2007年10月自学考试02142《数据结构导论》试题

数据结构导论模拟试题

（一）单项选择题

1. 在二维数组中，每个数组元素同时处于（）个向量中。

A. 0

B. 1

C. 2

D. n

2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B 整体连接到A的末尾，其时间复杂度应为（）。

A. O(1)

B. O(m)

C. O(n)

D. O(m+n)

3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front == rear

B. front != NULL

C. rear != NULL

D. front == NULL

4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。

A. 3,2,1

B. 2,1,3

C. 3,1,2

D. 1,3,2

5. 图的广度优先搜索类似于树的（）遍历。

A. 先根

B. 中根

C. 后根

D. 层次

6. 下面程序段的时间复杂度为( )。

for(int i=0; i

for(int j=0; j

A. O(m2)

B. O(n2)

C. O(m*n)

D. O(m+n)

7. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。

A. 求子串

B. 模式匹配

C. 串替换

D. 串连接

8 利用双向链表作线性表的存储结构的优点是（）。

A. 便于单向进行插入和删除的操作

B. 便于双向进行插入和删除的操作

C. 节省空间

D. 便于销毁结构释放空间

9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。

A. top->link=s;

B.s->link=top->link; top->link=s;

C. s->link=top; top=s;

D. s->link=top; top=top->link;

10. 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为-1。

A. 5

B. 6

C. 7

D. 8

11. 一个有n个顶点和n条边的无向图一定是( ) 的。

A．连通 B．不连通 C．无回路 D．有回路

12. 在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（）。

A. O(n)

B. O(n/2)

C. O(1)

D. O(n2)

13. 已知广义表为A((a,b,c),(d,e,f))，从A中取出原子e的运算是（）。

A．Tail(Head(A)) B．Head(Tail(A))

1

02142

C．Head(Tail(Head(Tail(A)))) D．Head(Head(Tail(Tail(A))))

14. 在一棵树的静态双亲表示中，每个存储结点包含( )个域。

A 1

B 2

C 3

D 4

15. 有向图中的一个顶点的度数等于该顶点的( )。

A．入度 B．出度

C．入度与出度之和 D．(入度+出度)/２

15. 与邻接矩阵相比，邻接表更适合于存储( )。

A．无向图 B．连通图 C．稀疏图 D．稠密图

17. 较快的数据搜索方法是（）搜索方法。

A. 顺序

B. 折半

C. 单链

D. 散列

18. 在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的。

A. 同义词之间发生冲突

B. 非同义词之间发生冲突

C. 同义词之间或非同义词之间发生冲突

D. 散列表“溢出”

19. 根据n个元素建立一个有序单链表的时间复杂度为（）。

A. O(1)

B. O(n)

C. O(n2)

D. O(nlog2n)

20. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front+1==rear

B. rear+1==front

C. front==0

D. front==rear

21. 假定一棵二叉树的第i层上有3i个结点，则第i+1层上最多有( )个结点。

A. 3i

B. 6i

C. 9i

D. 2i

22. 对于具有e条边的无向图，它的邻接表中共有( )个边结点。

A．e-1 B．e+1 C．2e D．3e

23. 图的深度优先搜索遍历类似于树的（）次序遍历。

A. 先根

B. 中根

C. 后根

D. 层次

24．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?( )

A. E、D、C、B、A、F

B. B、C、E、F、A、D

C. C、B、E、D、A、F

D. A、D、F、E、B、C

25．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：( )

A. 98

B. 99

C. 50

D. 48

26. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：( )

A. {21、25、5、17、9、23、30}

B. {25、23、30、17、21、5、9}

B. {21、9、17、30、25、23、5}

D. {5、9、17、21、23、25、30}

27．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为( )

A. 顺序表

B. 用头指针表示的单循环链表

C. 用尾指针表示的单循环链表

D. 单链表

28．假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：( )

A. (A, C, D, F, H, M, P, Q, R, S, X, Y)

B. (A, F, H, C, D, P, M, Q, R, S, Y, X)

C. (F, H, C, D, P, A, M, Q, R, S, Y, X)

D. (P, A, M, F, H, C, D, Q, S, Y, R, X)

29．下面是三个关于有向图运算的叙述：( )

2

02142

（1）求有向图结点的拓扑序列，其结果必定是唯一的

（2）求两个指向结点间的最短路径，其结果必定是唯一的

（3）求AOE网的关键路径，其结果必定是唯一的

其中哪个（些）是正确的？

A. 只有（1）

B. （1）和（2）

C. 都正确

D. 都不正确

30．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: ( )

A. 4

B. 5

C. 6

D. 7

31. 以下关于广义表的叙述中,正确的是：( )

A. 广义表是由0个或多个单元素或子表构成的有限序列

B. 广义表至少有一个元素是子表

C. 广义表不能递归定义

D) 广义表不能为空表

32. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？( )

A. 堆排序

B. 直接插入排序

C. 快速排序

D. 冒泡排序

33．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：( )

A. 将邻接矩阵的第i行删除

B. 将邻接矩阵的第i行元素全部置为0

C. 将邻接矩阵的第i列删除

D. 将邻接矩阵的第i列元素全部置为0

34．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：( )

A. head->priro==NULL

B. head->next==NULL

C. head->next==head

D. head->next-> priro==NULL

35. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 )中，用折半法查找关键码值11，所需的关键码比较次数为：( )

A. 2

B. 3

C. 4

D. 5

36. 以下哪一个不是队列的基本运算？( )

A. 从队尾插入一个新元素

B. 从队列中删除第i个元素

C. 判断一个队列是否为空

D. 读取队头元素的值

37．对包含n个元素的哈希表进行查找，平均查找长度为：( )

A. O(log2n)

B. O(n)

C. O(nlog2n) D 不直接依赖于n

38．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：( )

A. 48

B. 49

C. 50

D. 51

39．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：( )

A. 3

B. 2

C. 4

D. 5

40．下面是顺序存储结构的优点。

A. 存储密度大

B. 插入运算方便

C. 查找方便

D. 适合各种逻辑结构的存储表示

41．下面关于串的叙述中，是不正确的。

A. 串是字符的有限序列

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储

42．的邻接矩阵是对称矩阵。

A. 有向图

B. 无向图

C. AOV网

D. AOE网

43．用链式方式存储的队列，在进行删除运算时，。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

3

02142

44．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是。

先序序列：EFHIGJK 中序序列：HFIEJKG

A. E

B. F

C. G

D. H

45．下面方法可以判断出一个有向图中是否有环。

A. 深度优先遍历

B. 拓朴排序

C. 求最短路径

D.求关键路径

46．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。

A. 插入

B. 选择

C. 冒泡

D. 都不是

47．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是。

A. edcba

B. decba

C. dceab

D. abcde

48．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是。

A. i

B. 2*i<=n

C. 2*i+1>n

D. 2*i>n

49．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。

A. 64.5

B. 64

C. 63

D. 65

50．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行。

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

B. p->next=q->next; q=p;

C. p->next=p->next; q->next=q;

D. p->next=q->next; q->nxet=p;

51．对一个满二叉树，m个树叶，n个结点，深度为h，则有。

A. n=h+m

B. h+m=2n

C. m=h-1

D. n=2h-1

52．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。

A. 选择排序

B. 冒泡排序

C. 插入排序

D. 希尔排序

53．用链式方式存储的队列，在进行插入运算时，。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

54．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移个元素。

A. n-i

B. n-i-1

C. n-i+1

D. i

55．一个栈的入栈序列是12345，则栈的不可能的输出序列是。

A. 23415

B. 54132

C. 23145

D. 15432

56．5个顶点的有向图最多有条弧。

A. 5

B. 20

C. 4

D. 25

57．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为。

A. front==rear

B. front!=NULL

C. rear!=NULL

D. front==NULL

58．若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（）存储方式最省时间。

A.单链表

B.双链表

C.单向循环链表

D.顺序表

59．将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（）。

A. 34

B. 35

C. 33

D. 无法确定

60. 单循环链表的主要优点是（）。

4

02142

A. 不再需要头指针了

B. 已知某结点的位置后，很容易找到其前驱

C. 在进行插入、删除运算时，能更好地保证链表不断开

D. 从表中任一结点出发都能扫描到整个链表

61. 一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（）。

A. 5、4、3、2、1

B. 4、5、3、2、1

C. 4、3、5、1、2

D. 1、2、3、4、5

62. 串是一种特殊的线性表，其特殊性表现在（）。

A. 可以顺序存储

B.数据元素是一个字符

C可以链式存储 D.数据元素是多个字符

63. n个顶点的无向图中最多有（）条边。

A. n(n-1)/2

B. n(n-1)

C. n(n+1)

D. n(n+1)/2

64. 6个顶点的无向图中，至少有（）条边才能保证是一个连通图。

A. 5

B. 6

C. 7

D. 8

65．若某线性表中最常用的操作是删除第1个元素，则不宜采用（）存储方式。

A.单链表

B.双链表

C.单向循环链表

D.顺序表

66．在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子，则其右孩子的编号为（）。

A. 2i

B. 2i-1

C. 2i+1

D. i/2

67. 按照二叉树的定义，具有3个结点的二叉树有（）种不同形态。

A. 3

B. 4

C. 5

D. 6

68. 在长为n的顺序表中，删除第i个元素(1≤i≤n+1)需要向前移动（）个元素。

A. n-i

B. n-i+1

C. n-i-1

D. i

69. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（）。

A. 5、4、3、2、1

B. 4、5、3、2、1

C. 4、3、5、1、2

D. 1、2、3、4、5

70. 栈是一种特殊的线性表，其特殊性表现在（）。

A. 可以顺序存储

B.只能从端点进行插入和删除

C. 可以链式存储

D. 可以在任何位置进行插入和删除

71. 一棵二叉树中，第k层上最多有（）个结点。

A. 2k

B.2k-1

C.2k

D.2k-1

72. 一棵有18个结点的二叉树，其高度最小为（）层。

A. 4

B. 5

C. 6

D. 18

73.有向图中，所有顶点入度和是所有顶点出度和的（）倍。

A. 0.5

B. 1

C. 2

D. 4

（二）填空题

1.数据元素之间存在的相互关系称为。

2.数据结构从逻辑上分为结构和结构。

3.线性表的顺序存储结构称为。

4.所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为。

5.深度为h的二叉树,最少有个结点。

6.折半查找要求待查表为表。

7.n个记录按其关键字大小递增或递减的次序排列起来的过程称为。

5

02142

8.存储数据时,不仅要存储数据元素的 ,还要存储元素之间的相互。

9．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为_ ___。

10、一个字符串相等的充要条件是和。

11、在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有

和_ 结点。

11、在一个长度为n 的顺序表中向第 i 个元素（0

要向后移动_ 个元素。

12、_ 是只允许在表的一端进行插入，而在另一端进行删除的线性表。

13、设主串T＝“abxxyxyxxbaa”,模式串P＝“xyxx”则第_ 次匹配成功。

14、在一棵二叉树中，第5层上的结点数最多为_ 。（根的层次为1）

15、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组中，其中B［0］存储

矩阵中第1个元素a1,1 ，则B[31] 中存放的元素是_ 。

16、有n个结点的二叉链表中，其中空的指针域为n+1，指向孩子的指针个数为_ 。

17、二叉树后序遍历的顺序是ABCDE，则该二叉树的根结点是_ 。

18、对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则整个邻接表中的结

点总数是_ 。

19、在单链表上难以实现的排序方法有_ 和_ 。

20、_ 查找法的平均查找长度与元素个数n无关。

21、在有n 个元素的顺序表的任意位置插入一个元素所需移动结点的平均次数为

_ 。

22、_ 是插入和删除元素都在表的同一端进行的线性表。

23、广义表L＝（a,b,c,L）,则其长度为_ 。

24、在树中，除跟结点外，其他结点都有且只有一个_ 结点。

26、在串s=“structure”中，以t 为首字符的子串有_ 个。

27、广度优先搜索遍历类似于树的按_ 遍历的过程。

28、已知一棵完全二叉树中共有768个结点为，则该树中共有_ 个叶子结点。

29、在有序表（12,24,36,48,60,72,84）中二分查找关键字72时所需进行的关键字比较次

数为_ 。

30、两个长度分别m和n（m>n）的排好序的表归并成一个排好序的表，至少要进行_ 次

键值比较。通常从四个方面评价算法的质量：_________、_________、_________和_________。

31、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

32、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指

针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。

33、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点

分别有_______个和________个。

34、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有

向完全图中，包含有________条边。

35、36.在快速排序、堆排序、归并排序中，_________排序是稳定的。

36、37.中序遍历二叉排序树所得到的序列是___________序列。

38.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。

39.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立

的初始堆为___________________________。

40．数据的物理结构主要包括________和________两种情况。

6

02142

41.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作

为该完全二叉树的存储结构，则共有___________个空指针域。

42、设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

43、设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和

等于顶点i的____，第i列上所有元素之和等于顶点i的____。设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

44、设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为

_________。

45、__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或

后序）。

46、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较

________次就可以断定数据元素X是否在查找表中。

47、不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为

____________。

48、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第

i个结点的双亲结点编号为________，右孩子结点的编号为________。

49、设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的

一趟快速排序结果为__________________。

50、设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图

的一种拓扑序列为____________________。

51、下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

} j+1，hashtable[j].key==k

52、下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild;

else_____________;

}

return(t)，t=t->rchild

53、设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平

均时间复杂度为_________。

54、设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为

_________________________________________________________（设结点中的两个指针域

7

02142

分别为llink和rlink）。根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____ 3_______。

55、深度为k的完全二叉树中最少有____ 2k-1____个结点。

56、设初始记录关键字序列为(K1，K2，…，K n)，则用筛选法思想建堆必须从第__ n/2_个元

素开始进行筛选。

59、设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为

存储结构，则该树中有_____个空指针域。

60、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队

列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

61、设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_____

个数据元素；删除第i个位置上的数据元素需要移动表中_____个元素。

62、设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速

排序结果为______________________________。

63、设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列

建成的初始堆为________________________。

64、设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0

元素的个数（填等于，大于或小于）。

65、设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该

二叉树的序列为_____________。

66、设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上

正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist;

void createlkhash(lklist *hashtable[ ])

{

int i,k; lklist *s;

for(i=0;i

for(i=0;i

{

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________;

}

}

hashtable[i]=0，hashtable[k]=s

三、应用题主要考点

1、二叉树的遍历与恢复（即已知二叉树对其遍历、已知遍历序列恢复二叉树）、哈夫曼树的

构造

2、图的存储结构（邻接矩阵、邻接表）、图的应用（最小生成树、拓扑排序）

3、各种查找方法（二叉排序树、散列表、平均查找长度）

4、各种排序方法

8

四、算法设计题主要考点

1、线性表的简单算法(顺序表和单链表的基本运算)。

2、二叉树的简单应用算法(如二叉树的遍历、求二叉树的高度、二叉树中叶子节点数等)。

3、查找算法（顺序查找、二分查找）。

4、排序算法（如插入、交换、选择排序等）。

9