国家开放大学(数据结构)章节练习(2020.05.02)

单项选择题
数据结构中，与所使用的计算机无关的是数据的（）。
A.物理结构
B.逻辑结构
C.物理和存储结构
D.存储结构
问答题
给出G的邻接矩阵和邻接表。
答案：
填空题
在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r->next=s；和（）（结点的指针域为next）。
答案：r->next=s；
单项选择题
若让元素1，2，3依次进栈，则出栈顺序不可能为（）。
A. 2，1，3
B. 3，1，2
C. 3，2，1
问答题
试给出用归并排序法对该序列作升序排序时的每一趟的结果。
答案：初始 11，19，5，4，7，13，2，10
第一趟[11，19][4，5][7，13][2，10]
问答题
说明成功查找到元素40需要经过多少次比较？
答案：4次
单项选择题
判断一个顺序队列（最多元素为m）为空的条件是（）。
A.rear==m-1
B.front==rear+1
C.front==rear
问答题
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是多少？
答案：出队序列是e2，e4，e3，e6，e5，e1的过程：
（1）e1入栈（栈底到栈顶元素是e1）
（2）...
填空题
设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为9，该完全二叉树一共有（）个结点。
答案：18
问答题
以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1，2，3，……，n，完成程序中空格部分。
答案：
（1）p
（2）q=p
（3）（NODE*）malloc（sizeof（NODE））
（4）p
（5）q=p