数据结构（本）期末综合练习（2013年12月）(3)

1．（1） a

c b

d e

图8

（2）d 2．

(1) 用顶点表示活动，边表示活动间先后关系的有向图称为顶点活动网

在顶点活动网中，若不存在回路,则所有活动可排列成一个线性序列,使每个活动的所 有前驱活动都排在该活动的前面,称此序列为拓扑序列 (2) abdc adbc dabc

(3) 在 b和d间添加有向边 3．（1） 42 16

67 32 82 42

102 16 32 57 82 67 57 52 102 52 初始树堆 图9

（2）102，52，42，82，16，67，32，57

4．

11

(1) A7 A4 A8 A2 A5 A9 A1 A3 A6 1 2 3 4 5 6 7 8 9 (2) 8 5 1

（3）

7 4 8 2 5 3 6 9 1 9.5

图10

5.

16 1319 11 14 17 2012 15 18 21

图11

(2) 4次 2次 （3）3次 4次

（4）11，12，13，14，15，16，17，18，19，20，21

12

6. (1)见图12

(2) 15,16,14,19,18,28,30,26,17 (3) 14,15,16,17,18,19,26,28,30

17 (4) 4

四、程序填空题 1. (1) n

(2) (s+j)/2; (3) j=m-1; (4) s=m+1; (5) a[k+1] 2．（1）NULL

（2）k

（3）p=p->left （4）p=p->right （5）p 3

（1）sizeof (struct node) （2）p->next=top （3）top=p 4.

(1)q->next!=NULL (2) p=p->next; (3)q->next=s;

14 26 16 18 30 15 19 28 图12

期末综合练习二

13

一、单项选择题

1. 在数据结构和算法中，与所使用的计算机有关的是 （ ）。 A．数据元数间的抽象关系 B．数据的存储结构 C．算法的时间复杂度 D．数据的逻辑结构 2. 一种逻辑结构在存储时（ ）。

A．只要存储数据元素间的关系 B．只能采用一种存储结构 C．可采用不同的存储结构 D．只要存储数据元素的值 3 .对顺序表,以下叙述中正确的是 ( )。

A．用一组地址连续的存储单元依次存放线性表的数据元素 B．各个数据元素的首地址是连续的

C．数据元素不能随机访问 D．插入操作不需要移动元素 4 .对链表,以下叙述中正确的是（ ）。

A．不能随机访问任一结点 B．结点占用的存储空间是连续的

C．插入删除元素的操作一定要要移动结点 D．可以通过下标对链表进行直接访问 5．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为 （ ）。

A．9 B．10 C．15 D．16

6．线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结点，则采用（ ）存储方式是不可行的。

A．单链表 B．双链表 C．单循环链表 D．顺序表 7.设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( )。

A.p->next=p->next->next;

B.p=p->next;

C.p=p->next->next; D.p->next=p ; 8．栈和队列的共同特点是（ ）。

A．都是先进后出 B．元素都可以随机进出

C．只容许在端点处插入和删除元素 D．都是先进先出

9．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的可能输出序列是（ ）。（进栈出栈可以交替进行）。 A．7，5，3，1 B．7，3，1,5

C．7，5，1，3 D．5,1，3，7

10．元素2，4，6，8按顺序依次进栈，按该栈的的可能输出序列依次入队列，该队列的可能

输出序列是（ ）（进栈出栈可以交替进行）。 A．8，6，2，4 B．8，4，2，6

C．6，2，4，8 D．8，6，4，2

11 ．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（ ）。 A．p=top->next; top=top?next; B．p->next=top; C．p->next=top;top=p; D．top=p;

12．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一 个结点并把结点的值保存在变量x中的运算为（ ）。 A．x=r?data；r=r?next; B．r=r?next;x=r?data C．x=f?data；f=f?next; D．f=f?next;x=f?data

14

13．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）

A．a7,6 B．a10,8C．a9,2 D．a8,5

14．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是（ ）。(矩阵中的第1个元素是a1,1 ）

A．a10,8 B．a7,6 C．a9,2 D．a8,5

15．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则矩阵中元素

a10,6 在一维数组B中的下标是

（ ）。(矩阵中的第1个元素是a1,1 ）

A．45, B．18 C．51 D．53 16．在C语言中，分别存储 “S”和‘s’，各需要占用（ ）字节。 A．一个和两个 B．两个 C．一个 D．两个和一个 17．串函数StrCmp（“ABCd”，“ABCD”）的值为（ ）。

A．0 B．-1 C．1 D．3

18．一棵有n个结点，采用链式存储的二叉树中，共有（ ）个指针域被有效使用（即指针域为非空）。

A．n+1 B．n C．n-1 D．n-2

19．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（ ）个结点。 A．n+1 B．n C．n-1 D．n-2

20．在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（ ）。 A．i/2.0B．i/2向下取整C．2i+1 D．i+2

21．设一棵哈夫曼树共有n个非叶结点，则该树有（ ）个结点。

A．2n B．2n+2 C．2n-1 D．2n+1 22．设一棵哈夫曼树共有2n+1个结点，则该树有（ ）个非叶结点。 A．n B．n+1 C．n-1 D．2n

23．一棵 结点数31

24．一棵完全二叉树共有4层，且第4层上有2个结点，该树共有（ ）个非叶子结点

(根为第一层)。

A．5B．4C．3D．9

25．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到

的一种顶点序列为（ ）。

A．abedfc B．acfebd C．aebcfd D．aedfbc

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构（本）期末综合练习（2013年12月）(3)在线全文阅读。