数据结构复习题

阜阳师范学院 2013 ——

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 题 号 得 分 阅卷教师签名 第一部分 选择题

1.计算机算法必须具备输入、输出和( )等5个特性。

A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性 2.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B．p->next=s->next;p->next=s; C．p->next=s;p->next=s->next; D．s->next=p->next;p->next=s; 3.数据结构在计算机内存中的表示是指（ ） A．数据结构

B．数据的逻辑结构 D．数据元素

一

2014 学年度第 二 学期复习题

份,

八 年 月 日

九 十

考试，任课教师 十一 十二

拟题 总 分 备 注 专业 二 数据结构 三 四 课程，共 20 页， 第1页，共印刷

五 六 七 学号 C. 线性结构、非线性结构 D.初等结构、构造型结构 9.算法分析的两个主要方面是：（ ）

A． 空间复杂性和时间复杂性 B.正确性和简明性 C． 可读性和文档性 D.数据复杂性和程序复杂性 10.计算机算法指的是：（ ）

A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法

11.一个顺序表由（a0,a1,a2,?an-1）n个元素构成，a0存储地址是100，每个元素的长度为2，则a4元素的地址是（ ）

A.110 B.108 C.100 D.120

12.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元

班 姓名 C．数据的存储结构

级 4.L是一个带头结点的空单向循环链表，若要向L中插入一个由指针p指向的结点，则执行（ ）。 素。 A.L=p; p->next=L; B. L->next=p; p->next=L; A.8 B.63.5 C.63 D.7 C. p->next=L; p=L; D.p->next=L->next; L=p;

5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带头结点的双循环链表 D.带尾指针的单循环链表

6.在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储（ ） A. 数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法

7.若要在0(1) 的时间复杂度上，通过两个单向循环链表的头尾相接实现合并，则应对两个循环链表各设置一个指针，分别指向( )。 A. 各自的头结点

B. 各自的尾结点

D.一个表的头结点，另一个表的尾结点

13.线性表Ｌ在( )情况下适用于使用链式结构实现。

Ａ.需经常修改Ｌ中的结点值 Ｂ.需不断对Ｌ进行删除插入 Ｃ.Ｌ中含有大量的结点 Ｄ.Ｌ中结点结构复杂

14.在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 15.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 16.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( ) A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以

17.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表。

学院 C. 各自的第一个元素结点。

8.从逻辑上来分，数据结构可以分为（ ）两大类。

A. 动态结构、静态结构 B.顺序结构、链式结构

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 专业 18.与单链表相比，双向链表的优点之一是（ ）

数据结构 课程 共 20 页，第 2 页，共印刷 份, 年 月 日 考试，任课教师

27.设某线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现效率更高。

A.输出第i个元素（1<=i<=n） C.顺序输出这n个元素的值 28.算法的时间复杂度是指（ ） A．算法执行的绝对时间

B．随着问题规模n的增大，算法执行时间的增长趋势。 C．算法中执行语句的条数 D．获得算法执行时间的复杂程度。

B.交换第1个元素和第二个元素的值

D.输出与给定值x相等的元素在线性表中的序号

A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头或表尾指针 D.访问前后结点更灵活

19.在双向链表中，删除P结点的操作（ ）（结点空间释放语句省略） A.p->prior->next=p->next; p-> next -> prior =p-> prior

B. p-> prior= p-> prior -> prior; p-> prior -> prior=p; C. p-> next -> prior =p; p->next= p-> next ->next;

D. p-> next= p-> prior -> prior; p-> prior= p-> prior -> prior;

20.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。

29.数据结构是指（ ）

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;

A．数据的基本单位

B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

B．性质相同的数据元素的集合

C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

C．相互之间存在一种或多种特定关系的数据元素集合 D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

D．描述客观事物且由计算处理的数值、字符等符号的总称 21.以下说法错误的是（ ）。

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的30.已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n 的降序链表，则最效率低

B．顺序存储的线性表可以随机存取

C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构

22.若一个算法的时间复杂度用T(n)表示，其中n 的含义是（ ） A．问题规模 B．语句条数 C．循环层数 D．函数数量

23.将长度为n 的单链表连接在长度为m 的单链表之后，其算法的时间复杂度为（ ） A．O(1)

B．O(m)

C．O(n)

D．O(m+n)

24.对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008 和h(n)=8888nlogn+3n2，下列陈述中不成立的是（ ） A．f(n)是0(g(n)) 程序 段是（ ）

A．p->next=r； q->next=r->next； r->next=q； B．p->next=r； r->next=q； q->next=r->next； C．r->next=q； q->next=r->next； p->next=r； D．r->next=q； p->next=r； q->next=r->next；

26.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表

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

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

B．g(n)是0(f(n))

C．h(n)是0(nlogn)

D．h(n)是0(n2)

25.指针p、q 和r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的

坏情况下的时间复杂度是（ D ） A. O(n) B. O(m

n) C. O(min(m,n)) D. O(max(m,n))

31.对于栈操作数据的原则是（B）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

32.设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D ）。

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4

33.一个递归算法必须包括（ B）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 34.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。

A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈

35.用带头结点的单链表存储队列时，在进行删除运算时（B）。

A. 仅修改头指针 B. 可能要修改尾指针

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

36.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。

A．仅修改队头指针 B. 仅修改队尾指针

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

37.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A)。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 38.栈和队列的共同点是（ C）。

A. 都是先进先出 B. 都是先进后出

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 专业 数据结构 C. 只允许在端点处插入和删除元素 D. 没有共同点 39.栈的插入和删除操作在（A）进行。

课程 共 20 页，第 3 页，共印刷 份, — 年 月 日 考试，任课教师 51. 若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（C）。

A．i B．n-i C．n-i+1 D．不确定

A．栈顶 B．栈底 C．任意位置 D．指定位置

40.元素a,b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出52.链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x

中,则应执行操作（A）。 栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（B）

A．x=top->data;top=top->link； B．top=top->link;x=top->link； A. 3 B. 4 C. 5 D.6 41.已知循环队列存储在一维数组A[0..n-l] 中，且队列非空时，front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第l 个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是（B）

A. 0, 0

B. 0, n-1 C. n-l ,0

D. n-1 , n-1

42.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立

即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（C）

A. 1 B. 2 C. 3 D. 4 43.若元素a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是（D）

A.d,c,e,b,f,a B.c,b,d,a,e,f

C.b,c,a,e,f,d

D.a,f,e,d,c,b

44.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（C）

A.b,a,c,d,e B.d,b,a,c,e C.d,b,c,a,e D.e,c,b,a,d 45.若用一个大小为 6 的数组来实现循环队列，且当前的 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再插入两个元素后，rear 和 front 的值分别为（B）。 A. 1，5 B. 2，4 C. 4，2 D. 5，1 46.最不适合用作链队的链表（ ）

A．只带队头指针的非循环双链表 B．只带队头指针的循环双链表

C．只带队尾指针的循环双链表

D．只带队尾指针的循环单链表

47.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50 个元素，则队列的尾指针值为（B）

A．3 B．37 C．50 D．97 48.数组A[ 1?5 ，l?6]的每个元素占4 个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[4，4]的地址是（ ）

A. 1175 B. 1180 C. 1088 D. 1084 49.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为(C) A．前序遍历 B．后序遍历 C.中序遍历 D.层次遍历 50.在一棵高度为k的满二叉树中，结点总数为（C）

k-1 k kk

A．2B．2C．2-1 D．?log2?+1

C．x=top;top=top->link；

D．x=top->link；

53.循环队列存储在数组A[0...m]中，则入队时的操作为（D）。

A. rear=rear+1 B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m D. rear=(rear+1)%(m+1)

54.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C）遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历

55.若一棵二叉树的前序遍历序列和后序遍历序列分别是1，2，3，4和4，3，2，1，同该二叉树的中序遍历列不会是（C）

A．1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 56.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（B）

I．父子关系 II.兄弟关系 III.u 的父结点与v 的父结点是兄弟关系

A.只有II B.I 和II C.I 和III D.I、II 和III

57.已知一棵有2011个结点的树，其叶结点的个数为116，该树对应的二叉树中无右孩子的结点个数是( D )

A.115 B.116 C.1895 D.1896 58.对n(n>=2)个权值均不相同的字符构成赫夫曼树,关于该树的叙述中,错误的是（A）

A．该树一定是一棵完全二叉树

B．树中一定没有度为1 的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值 59.一棵完全二叉树的结点总数为28，则该完全二叉树的深度为（）。

A.4 B.)5 C.6 D.7

60.一棵树高为K的完全二叉树至少有（ C）个结点

kk-1k-1k

A．2 –1 B. 2 –1 C. 2 D. 2

61. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定

62. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）

A．所有的结点均无左孩子 B．所有的结点均无右孩子

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 4 页，共印刷 份, — 年 月 日 考试，任课教师 C．只有一个叶子结点 D．是任意一棵二叉树 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 63.n个结点的线索二叉树上含有的线索数为（C） 76.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空

A．2n B．n－l C．n＋l D．n 的结点有（C）个。 A． n-1 B．n C． n+1 D． n+2

77.将一棵有 50 个结点的完全二叉树按层编号，则对编号为 25 的结点 x，该结

点 ( B )。 C.只有左子树上的部分结点 D.只有左子树上的所有结点

A．无左、右孩子 B．有左孩子，无右孩子 65.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对

C．有右孩子，无左孩子 D．有左、右孩子 应的二叉树根结点的右子树上的结点个数是（D）。

78.在下述结论中，正确的是（D） A．M1 B．M1+M2 C．M3 D．M2+M3

①只有一个结点的二叉树的度为0; 66.在由4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，

②二叉树的度为2； 当把森林转换成二叉树后，对应的二叉树中根节点的左子树中结点个数为（B）。

③二叉树的左右子树可任意交换; A． 64 B．29 C．30 D．4

④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 67.在一棵度数为4 的树T 中,若有20 个度为4 的结点,10 个度为3 的结点,1 个度为2 的结

A．①②③ B．②③④ C．②④ D．①④ 点,10 个度为1 的结点,则树T 的叶结点个数是（B ）

79.具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，A.41 B.82 C.113 D.122

其余(D) 个指针域为空。

68.已知一棵完全二叉树的第6 层（设根为第1 层）有8 个叶结点，则该完全二叉树的结点个数

A. 50 B. 99 C. 100 D.101

最多是（C）

80.由权值分别为4,8,6,3,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A．39 B.52 C.111 D.119

A.24 B.36 C.49 D.59

69．若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（C）

81.根据使用频率为5 个字符设计的哈夫曼编码不可能是( ) 。

A．257 B.258 C.384 D.385

A. 000, 001 , 010, 011 , 1 B. 0000, 0001 , 001 , 01 , 1

70.层次遍历一个完全二叉树的序列是：abcdefghij,则先序遍历序列为(B)

C. 000, 001 , 01 , 10, 11 D. 00, 100, 101 , 110, 111

A.abcdefghij B.abdhiejcfg C.acfgbejdhi D.acbgfedjih

82.一个栈的入栈序列为1, 2,3,?,n ，其出栈序列是p1,p2,p3，?pn。若p2=3，则p3可能取值的

71.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（ A ）。

个数是(C )

A． 不发生改变 B．发生改变 C．不能确定 D．以上都不对

A. n-3 B. n-2 C. n-1 D. 无法确定

83.已知三叉树T 中6 个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小72.在下述论述中，正确的是(D)。

①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换； ④是(B)

A. 27 B. 46 C. 54 D. 56 深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。

84.若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y，则X 的右线索指向的是（ A ） A．①②③ B．②③④ C．②④ D．①④

A. X 的父结点 B. 以Y 为根的子树的最左下结点 73.二叉树先序遍历和中序遍历如下：先序序列：EFHIGJK中序序列：HFIEJKG

C. X 的左兄弟结点Y D. 以Y 为根的子树的最右下结点 该二叉树根的右子树的根是（C） 64.在一非空二叉树的中序遍历序列中,根结点的右边( )

A.只有右子树上的所有结点 B.只有右子树上的部分结点

A.E B.F C.G D.H

74.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（C）。

A．X的双亲 B．X的右子树中最左的结点 C．X的左子树中最右结点 D．X的左子树中最右叶结点 75.引入二叉线索树的目的是（A）。

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除

85.设无向图的顶点个数为n，则该图最多有（ ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 86.一个n个顶点的连通无向图，其边的个数至少为（ ）。

A．n-1 B．n C．n+1 D．nlogn； 87.要连通具有n个顶点的有向图，至少需要（ ）条边。

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

2

计算机与信息 学院 信息工程、计科 专业 数据结构 …………….……………..装……………………订………………..线…………….…………….. 88．个结点的完全有向图含有边的数目（ ）。

课程 共 20 页，第 5页，共印刷 份, — 年 月 日 考试，任课教师 97.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法

构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D）个记录。

A．1 B. 2 C. 3 D. 4

98.设DFS(G,i)算法是对一个连通无向图进行深度优先遍历。若对某非连通无向图G访问所有顶点，则调用DFS(G,i)的次数正好等于（ ）。

A．顶点个数 B. 连通分量的数目 C. 边的数目 D.不确定

99.一个无向连通图中有13个顶点和16条边，所有顶点的度数均小于5，度为3的顶点有4个，度为2的顶点有2个，则度为4的顶点有（ ）个

A．2 B. 3 C. 4 D.5 100.下面关于哈希(Hash，杂凑)查找的说法正确的是( C )

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

89.在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

A．1/2 B．2 C．1 D．4 90.下列哪一种图的邻接矩阵是对称矩阵？（ ）

A．有向图 B．无向图 C．AOV网 D．AOE网 91.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( C )。

A. O(n) B. O(n+e) C. O(n) D. O(n)

92.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）

2

3

C．不存在特别好与坏的哈希函数，要视情况而定 A．0 1 3 2 B. 0 2 3 1

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即C. 0 3 2 1 D. 0 1 2 3

可

101.设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共

93.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）

A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(D ) A．8 B．3 C．5 D．9

102.已知关键序列5,8,12,19,28,20,15,22 是小根堆（最小堆），插入关键字3， 调整后得到的小根堆是（A） A．3,5,12,8,28,20,15,22,19 C．3,8,12,5,20,15,22,28,19

94.对线性表进行二分查找时，要求线性表必须（B ）

A.以顺序方式存储 C.以链接方式存储

B.以顺序方式存储,且数据元素有序 D.以链接方式存储,且数据元素有序

B. 3,5,12,19,20,15,22,8,28 D. 3,12,5,8,28,20,15,22,19

103.若数据元素序列11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第 二趟排序后的结果，则该排序算法只能是（B） A．起泡排序

B.插入排序

C.选择排序

D.二路归并排序

104.对下图进行拓扑排序,可以得到不同的拓扑序列的个数是(B)

A.4 B.3 C.2 D.1

95.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90，120，110，130） D. (100，80， 60， 90， 120，130，110) 96.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C) 型调整以使其平衡。

A. LL B. LR C. RL D. RR

…………….……………..装……………………订………………..线…………….…………….. 课程 共 20 页，第6页，共印刷 份, — 年 月 日 考试，任课教师

105.已知一个长度为16 的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在112.为提高散列（HASH）表的查找效率，可以采取的正确措施是（D） 的元素,则比较次数最多的是(B)

A.4

B.5 C.6 D.7

I．增大装填（载）因子

II．设计冲突（碰撞）少的散列函数

III．处理冲突（碰撞）时避免产生聚集（堆积）现象 A．仅I B．仅II C．仅I、II D．仅II、III 113.为实现快速排序算法，待排序序列宜采用的存储方式是（A）

A．顺序存储 B.散列存储 C.链式存储 D.索引存储

计算机与信息 学院 信息工程、计科 专业 数据结构 106.采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是(D)

A.递归次数于初始数据的排列次数无关

B.每次划分后,先处理较长的分区可以减少递归次数 C.每次划分后,先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区处理顺序无关

107.对一组数据(2,12,16,88,5,10)进行排序,若前三趟排序结果如下:

第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是( A)

A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法

108.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（A）

A．95，22，91，24，94，71 B．92，20，91，34，88，35 C．21，89，77，29，36，38 D．12，25，71，68，33，34 109.下列关于图的叙述中，正确的是（C）。

I．回路是简单路径

II．存储稀疏图，用邻接矩阵比邻接表更省空间 III．若有向图中存在拓扑序列，则该图不存在回路 A．仅II B．仅I、II C．仅III D．仅I、III 110.判断有向图是否有回路，除了可以用拓扑排序外，还可以用（ ）。

A．求关键路径的方法 C．求最短路径的方法

B．广度优先遍历算法 D．深度优先遍历算法

114.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（B）

A．1 B.2 C.4 D. 5 115.某内排序方法的稳定性是指( D)。

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 116.下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆积 117.下列排序算法中，其中（ D）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

118.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（C ）。

A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 119.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C)的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序

120.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( A )。

A. 选择 B. 冒泡 C. 快速 D. 插入

121.下列排序算法中( B)不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序

111.任何一个带权无向连通图的最小生成树是（ C）

A．一定是唯一的

B．一定不唯一的 D．有可能不存在的

C．有可能不唯一的

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 7 页，共印刷 份, 年 月 日 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 122.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A．(38,40,46,56,79,84) B. (40,38,46,79,56,84) C．(40,38,46,56,79,84) D. (40,38,46,84,56,79) 123.在下面的排序方法中，辅助空间为O（n）的是( D) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 124.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(C)排序。

A． 冒泡 B. 希尔 C. 快速 D. 堆

125.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序

126.如果在构造哈希表时采用链地址法解决冲突，且啥希函数为H(key)=key MOD 8则需要建造的链表数目是（ ）

A．6

B．5

C．8

D．9

132.堆排序是一种( B )排序。

Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并

133.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )

A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 134.下列二叉排序树中，满足平衡二叉树定义的是（B）

135.下列关于无向连通图特性的叙述中，正确的是（A ）

I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1

A.只有I B. 只有II C.I 和II D.I 和III

136.在下列所示的平衡二叉树中插入关键字48 后得到一棵新平衡二叉树,在新平衡二叉 树中,关键字37 所在结点的左、右子结点中保存的关键字分别是(C) A.13,48

B.24,48

C.24,53

D.24,90

127.下列因素中，影响排序算法稳定性关键因素是（B）。

I．待排元素个数的多少

II.排序过程中是否发生了不相邻元素的交换 III.是否有关键码相同的元素 IV.排序算法是否采用递归方式实现

A．仅I B．仅II C．I和III D．I和IV

128.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C）。

A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80

129.对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，137.用序列｛12，13，11，18，60，15，7，18，25，84｝构建初始堆，必须从关键字为（ ）8，20，9，7}则该次采用的增量是 ( B ) 的结点开始。

A. l B. 4 C. 3 D. 2 130.下列四个序列中，哪一个是堆（ C）。

A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 131,。链表适用于( A )查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机

A.84

B.12

C.60

D.15

138.关键路径是（ ） A.从源点到汇点的最长路径

B.从源点到汇点的最短路径

C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40

C.从源点到汇点的最长的回路 D.从源点到汇点的最短的回路

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 专业 139.在平衡二叉排序树中，每个结点（ ） A.左子树结点个数和右子树结点个数相差不超过1 B.平衡因子为0

C.左子树度数和右子树度数相差不超过1

数据结构 课程 共 20 页，第 8 页，共印刷 份, 年 月 日 — 考试，任课教师 148.一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。 A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图

149.若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则平衡二叉树的结点总数为 A.10

B.20

C.32

D.33

D.左子树深度（高度）和右子树深度（高度）相差的绝对值不超过1

140.排序过程中，元素的移动次数与各元素原始的排列顺序无关的排序方法是（ ）排序 A.简单选择排序 B.快速排序

C.堆排序

D.归并排序

141.如果（ ）则称这种排序方法是不稳定的

A.排序前后，排序码相同的元素在线性表中的相对位置可能会被颠倒 B.排序前后，排序码相同的元素在线性表中的相对位置一定会被颠倒 C.对同一个线性表，每次排序的结果可能不相同 D.排序的结果不可预测

142.用某种排序方法对关键字序列（23，22，21，47，15，27，59，35，20）进行排序时，前两

趟的结果情况如下：

22，23，21，47，15，27，59，35，20 21，22，23，47，15，27，59，35，20 则所采用的排序方法是（）。

A.堆排序 B.起泡排序 C.插入排序 D.快速排序 143.堆是一种有用的数据结构，下面的关键字序列（ ）是堆。 A.16，53，72，31，23，94 B.94，23，31，72，16，53 C.16，53，23，94，31，72 D.16，23，53，31，94，72

144.对以下关键字序列用快速排序法进行排序，速度最慢的是（ ）。 A.20，24，4，16，22，29

B.24,22，29，16，20，4，8

D.4，8，16，20，24，29

150.对有n个结点，e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是（ ） A.O(n)

B.O(e)

C.O(n+e)

D.O(n*e)

151.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结构是（ ）

A.存在且唯一

B.存在且不唯一 C.存在可能不唯一 D.无法确定是否存在

152.求最短路径的FLOYD 算法的时间复杂度为（ ）。 A.O(n) B.、O(n+e) C.O(n) D.O(n)

153.已知一个图中包含k个连通分量。如果按照深度优先搜索算法（DFS）遍历所有顶点，则必须调用该算法（ ）次 A.1

B. k-1

C. k

D.k+1

2

3

154.在最好和最坏情况下的时间复杂度均为O(nlogn) 且稳定的排序方法是( )。 A.快速排序 B. 堆排序 C. 归并排序 D. 基数排序

155.索引顺序表是将表分成若干子表(或称块)据此建立索引表，并要求关键字( )。 A. 块内有序，块间有序

B.块内无序，块间有序 D.块内无序，块间无序

C.块内有序，块间无序。

156.hash 函数为模运算，下面哪个值作为模数更好?（ ） A.1000 B. 1024 C. 972 D. 997

157.若从二叉树的任意结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（ ）

A.二叉排序树 B.完全二叉树 C. 堆 D. 平衡二叉树 158.在二叉排序树中，数值最小的结点是（ ） A.最左结点 C.根结点

B.最右结点 D.不确定

C.20，8，16，29，24，22，4

145.堆可以是大顶堆，也可以是小顶堆；下列序列中，（ ）既不是大顶堆，也不是小顶堆。 A.90，85，78，67，56，42，35，24，18 B.18，35，56，24，42，78，67，85，90 C.90，78，85，56，67，35，42，18，24 D.18，35，24，56，42，78，67，85，90 146.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ） A.G中有弧 C.G中没有弧

B.G中有一条从Vi到Vj的路径 D.G中有一条从Vj到Vi的路径

147.具有6个顶点的无向图，当有（ ）条边时能确保是一个连通图。 A.8

159.折半插入排序是对直接插入排序的改进，它着眼于减少（ ）

A.移动元素的次数

B.排序的趟数

B.9 C.10 D.11。

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 信息工程、计科 专业 数据结构 C.与关键字比较的次数 D.空间复杂度

课程 共 20 页，第 9 页，共印刷 份, 年 月 日 — 考试，任课教师 160.在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D ）位置上。 A．n/2

B．n/2 -1

C．1

D．n/2 +2

165.下列 AOE 网表示一项包含 8个活动的工程。通过同时加快若干进度可以缩短整个工程的工

C. 2

D. 3

期。下列选项中，加快其进度就可以缩短程是（ C ） A.c和e B. d和e C.f和d

D. f和h

161.若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0 的分支结点的个数是（ D ） A. 0

B. 1

162.在任意一棵非空二叉排序树T1 中，删除某结点v 之后形成二叉排序树T2，再将v 插入T2 形成二叉排序树T3。下列关于T1 与T3 的叙述中，正确的是（ C ） I. 若v 是T1 的叶结点，则T1 与T3 不同 II. 若v 是T1 的叶结点，则T1 与T3 相同 III. 若v 不是T1 的叶结点，则T1 与T3 不同 IV. 若v 不是T1 的叶结点，则T1 与T3 相同

A. 仅I、III B. 仅I、IV C. 仅II、III D. 仅II、IV 163.设图的邻接矩阵A 如下所示。各顶点的度依次是（ C ）

166.在一株高度为2的5阶B树中，所含关键字的个数最少是（A ） A.5

B. 7 C. 8 D. 14

167.对给定的关键字序列110，119，007，911，114，120，122进行基数排序，则第2趟分配收集后得到的关键字序列是（ C ）

A. 007，110，119，114，911，120，122 B. 007，110，119，114，911，122，120 C. 007，110，911，114，119，120，122

A. 1，2，1，2

B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，2

第二部分 填空题

1.程序段i=1; while(i<=n) i=i*3;的时间复杂度为 。

2．在长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素

3.带头结点的双循环链表L为空表的条件是： 。

4.以下程序的功能是实现带头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(LinkList h) // h为头结点指针； { LinkList p,q; p=h->next; h->next=NULL; while( _______)

{q=p; p=p->next; q->next=h->next; h->next= ________; }

}

D. 110，120，911，122，114，007，119

164.若对如下无向图进行遍历，则下列选项中，不．是广度优先遍历序列的是（ D ） A. h，c，a，b，d，e，g，f C. d，b，c，a，h，e，f，g

B. e，a，f，g，b，h，c，d D. a，b，c，d，h，e，f，g

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 10页，共印刷 份, 年 月 日 — 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 5.数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。

6.在如图所示的链表中，若在指针p 所指的结点之后插入数据域值相继为a 和b 的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。

24.图的逆邻接表存储结构只适用于 图。

25.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 。

26.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。

27.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。

28.在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中,需要内存量最

7.栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算大的是 。 的一端称为 栈底 。

29.，若查找表中元素20，它将依8. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 折半查找有序表（4，6，12，20，28，38，50，70，88，100）次与表中元素 比较大小。 9.如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_4_。 10.含4个度为2的结点和5个叶子结点的二叉树，可有__0至多____个度为1的结点。 11.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有___2n0-1___个结点。

30.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选用 。

12.以下程序为求二叉树深度的递归算法，请填空完善之。 31.大多数排序算法都有两个基本的操作： 和 。

int depth(bitree bt) /*bt为根结点的指针*/ 32.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找关键码值20，需做的{int hl,hr; 关键码比较次数为_ _. if (bt==NULL) return((1)___);

33.已知二叉排序树的左右子树均不为空，则_ _ _上所有结点的值均小于它的根结点值，__ ____

hl=depth(bt->lchild); hr=depth(bt->rchild);

上所有结点的值均大于它的根结点的值。 if((2)___) (3)_____；

34.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 return(hr+1); (1)0 （2）hl>hr (3)hr=hl 6-增量序列）依次是4，2，1则排序需__ _趟，写出第一趟结束后，数组中数据的排列次序_____ 13.一棵深度为6的满二叉树有 31 个分支结点和 23232 个叶子。

14.将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，_。 根结点的编号为0，则编号为50 的结点的右孩子编号为 。 35.具有10个顶点的无向图，边的总数最多为_ ___。 15.在计算机内实现递归算法时所需的辅助数据结构是 36.G是一个非连通无向图，共有28条边，则该图至少有 _个顶点。 16.若要在中序线索二叉树中找到左子树中序序列的最后一个结点， 则需要找其右指针指向 37.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__ __条弧 的结点。

38.在有n个顶点的有向图中，每个顶点的度最大可达_ _____。

17.设根的层次为1，则有64 个结点的完全二叉树的深度为

18.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必定也是该子树的39.设G为具有N个顶点的无向连通图，则G中至少有 条边。 _________序列中的最后一个结点。 40.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有__ ______个非零元素。 19.有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 20.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。 21.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。 22.设有一稀疏图G，则G采用 存储较省空间。 23.设有一稠密图G，则G采用 存储较省空间。

41.求图的最小生成树有两种算法，_ ____算法适合于求稀疏图的最小生成树。 42.在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为__ ____。 43.无向图中的一个极大连通子图称为它的一个________。 44._____________排序不需要进行记录关键字间的比较。

45.已知一组数据( 15 ，19, 17, 8, 20，25,7) , 用堆排序的筛选方法建立了初始小根:堆后，

则最后一个结点值为

…………….……………..装……………………订………………..线…………….…………….. 课程 共 20 页，第16页，共印刷 份, — 年 月 日 考试，任课教师

27.已知世界6 大城市：北京(B)、纽约(N) 、巴黎（p）、伦敦(L) 、东京(T)、墨西哥城（M)。第五部分 算法设计题

1. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 试在下表给出的交通网中确定最小生成树，并说明所使用的方法和时间复杂度。 表：世界6 大城市交通里程网络表(单位：1OOkm) B N P L T M

28.已知数据序列为(36，74，8，50，18，6，40，30)，给出建立二叉排序树的过程示意图，再给出删除74，8后的二叉排序树。

29.对下面的有向图。

1) 给出每个顶点的入度和出度 2) 画出邻接链表 3) 求所有可能的拓扑序

5 6 2 3 4 1 B 109 82 81 21 124 N 109 58 55 108 32 P 82 58 3 97 92 L 81 55 3 95 89 T 21 108 91 95 113 M 124 32 92 89 113 void delete（Linklist &L）

计算机与信息 学院 信息工程、计科 专业 数据结构 LinkedList Delete（LinkedList L）

∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null）

{if（p->next->datadata）{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移。 } pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。

2. 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存

储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next;

Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb){

if(pa->datadata){ pc->next=pa;pc=pa;pa=pa->next;}

else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素，删除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q;} } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点}

3. 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)

的算法，该算法删除线性表中所有值为item的数据元素。 void Delete_Sq(SqList &A)

计算机与信息 学院 信息工程、计科 专业 数据结构 link 课程 共 20 页，第 17 页，共印刷 份, 年 月 日 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 4. 已知一个带有表头结点的单链表，结点结构为： data 7. 已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，在非头结

点p所指元素前，插入元素e,并分析算法的时间复杂度。

假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K位置的结点（K为正整数），若查找成功，算法输出该结点 data域的值，并返回1，时间复杂度O(n) 否则只返回0；要求：

（1）简述算法的基本设计思想；

（2）描述算法的详细实现步骤（使用C，或C++实现 ），关键之处给出详细解释。 int LocateElement(linklist list,int k)

{ P1=list->link; P=list; i=1; while(P1) { P1=P1->link; i++;

if(i>k) P=P->next; //如果i>k,则p也往后移 }

if(P==list) return 0; //说明链表没有k个结点 else { printf(“%d\\n“,P->data); return 1; } }

5. 已知非空线性链表第一个结点的指针为list，请写一个算法，将该链表中数据域值最大的那

个结点移到链表的最后面。 void REMOVE(LinkList & list){ LinkList s,r,p,q; q=list; p=list->link; r=list; While(p!=NULL){ if(p->data->q->data) then

Delete(Node *L, Node *p)

{ Node *s, *t s = L->next; t = L; while (s != NULL && s != p){ t = s; s = s->next; }

if (s != NULL){ t->next = s->next; free(s);} }

8. 已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，删除非头

结点p所指元素,并分析算法的时间复杂度。

9. 试设计实现在单链表中删去值相同的多余结点的算法。

typedef int datatype;

{ s=r; q=p; } r=p;p=p->link;} typedef struct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head) if(q!=r) then { if (q==list) then list=q->link;

{ lklist *p,*q,*s;

else s->link=q->link; r->link=q; q->link=NULL; } } for(p=head;p!=0;p=p->next)

{ for(q=p->next,s=q;q!=0; )

6. 若已知非空线性链表第一个结点的指针为list，请 写一个算法，将该链表中数据域值最小的

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

那个结点移到链表的最前端。

else {s=q,q=q->next;}

void REMOVE(LinkList & list){ } }

LinkList q=list, s ,r; p=list->link ;

While(p!=NULL){ if(p->data->q->data) then { s=r; q=p; } r=p;p=p->link;}

if(q!=list) then s->link=q->link; q->link=list; list=q; } }

10. 编写算法，判断带头结点的双向循环链表L是否对称。对称是指：设各元素值a1,a2,...,an,

则有ai=an-i+1 ，即指：a1= an，a2= an-1 。。 。。。。。

结点结构为：

prior data next int judge(DLinkList L) {

p=L->next; q=L->prior; while(p!=q) {

if(p->data!=q->data) return 0; if(p->next==q) return 1; p=p->next; q=q->prior; } return 1; }

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 18 页，共印刷 份, 年 月 日 — 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 11. 已知带头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插

入链表L中，使L仍然有序。

分析：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下： void insertorder(Linklist &L， Elemtype x) { Linklist p,q,s; s=(Linklist)malloc(sizeof(Lnode));

s->data=x; s->next=NULL; //产生一个待插入的结点s q=L; p=q->next; while( p && x>p->data)

{ q=p; /使q始终指向p的前驱 p=p->next； } s->next=p; q->next=s; //将s结点插入到q和p之间 }

12. 假设线性表采用顺序存储结构，编写算法，将顺序表L 中所有值为奇数的元素调整到表的前

端。

viod f34 (Seqlist head) { int temp，m=0; for(i=0；ilength；i++)

{ if(p->data[i] mod 2 !=0) {temp=t->data[m]； t->data[m]= t->data[j]； t->data[i]=temp m++; } } }

13. 设L为带表头结点的单链表头指针，且表中结点的值均为正整数，试编写算法，实现将表中

值最小结点插入到值最大结点之前。

14. 设L为一无序的整数单链表。请设计算法,将链表L分成两个链表,一个用来存放值为奇 数的结点和一个用来存放值为偶数的结点。

15. 现有一个逆序排列的数据元素序列,用带头结点的单链表存储,已知头结点的地址存在h中,请

设计一个算法,能有效的按正序输出该序列。

16. 己知一个数据值为整数的线性表,欲以表中第一个数据元素为参考点,将该表划分为左右两

部分,使其参考点左边的每个数据元素值均小于参考点的值,而参考点右边的每个数据元素值均大于参考点的值。请设计一个求解该问题的有效算法。

17. 设有一整数序列由正数、负数组成，编写程序，通过一趟扫描处理，将所有的负数移到正数

前面，只能用一个辅助单元。写出算法思想。

18. 设一单链表，结点由整型数据和指针项组成，计算链表中数据只出现1次的结点个数，要求

空间复杂度为O(1)。编写程序，并写出算法思想。

19. 设包含4 个数据元素的集合S={ \，\，\，\，各元素的查 找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将S 保存在一个长度为4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：

（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用 何种查找方法？查找成功时的平均查找长度是多少？

（2）若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？应使用 何种查找方法？查找成功时的平均查找长度是多少？

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 19 页，共印刷 份, 年 月 日 — 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 20. 已知一个整数序列A= (a0, a1,?，an-1) ，其中0≤ai ＜ n(0 ≤ i＜ n) 。若存在a =?p=ap2 21.设二叉排序树bt以二叉链表为存储结构，试设计算法删除二叉排序树bt中值最大的结点。

=apm=x且m ＞n/2(0 ≤pk

if (!bt) return ERROR; //空树

5，5 )，则5 为主元素；又如A= ( 0，5，5，3，5，1，5，7 )，则A 中没有主元素。假设

p = bt;

A 中的n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A 的主元素。

if (bt->rchild == NULL){ //根无右子树 --------2分

若存在主元素，则输出该元素；否则输出-1。要求： bt = bt->lchild; p->lchild = NULL;//此语句可不要

free(p); } （1）给出算法的基本设计思想。

else{ while(p->rchild != NULL){//p移至最右下结点

（2）根据设计思想，采用C 或C++或Java 语言描述算法，关键之处给出注释。

q = p; p = p->rchild;}

（3

if(p->lchild != NULL)//有左子树 --------5分

（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为 主元素 的Num 。然 后重新计 q->rchild = p->lchild;

数 ，确认 NumNum 是否主元素。 算法可分为以下两步 ： ① 选取候的主元素 ：依次扫描所给 else q->rchild = NULL;//无左子树

free(p); } }//del_max

数 组中的每个整，将第一遇到Nu m保存 到 c中，记录 Nu m的出现次数为 的出现次数为 1；

22.假设无向图G，采用邻接表存储，编写程序，判断图G是否是连通图，若是连通图返回1，否

若遇到的下一个整数仍等于 NumNum ，则计数加 1， 否则计数减 1；当计数减到 0时，将遇到 的

则返回O。 写出算法思想。

下一个整数保存c中，计数重新记为 中，计数重新记为 1， 开始新一轮计数，即从当前位置重

复上述过程直到扫描完全部组元素。 ② 判断 c中元素 是否真正的主中元素 是否真正的主：再

次扫描该数组，统计 c中元素出现的次数，若 中元素出现的次数，若 大于 n/2 ，则为主元素 ；

否则，序列中不存在主元素。

（2）算法实现：（7分）

23.设二叉排序树中的结点值为整型，最大值为MAX， 给出任意整型值x ( x <=MAX)， 编写程

int Majority(int A[], int n)

序， 求二叉排序树中大于x 的最小一个数。（提示x不一定在树中）

{int i, c, count=1; / / c用来保存候选主元素，count用来计数

c = A[0]; / / 设置A[0]为候选主元素

for ( i=1; i

if ( A[i] = = c ) count++; / / 对A中的候选主元素计数

else if ( count > 0) / / 处理不是候选主元素的情况

24.设二叉排序树T 的key 值为整数，高度为k，对任意给定的整数x，查找元素值小于x 且最

count--;else / / 更换候选主元素，重新计数

接近x 的结点并返回结点指针，如该结点不存在则返回指针为空，要求用非递归算法实现且时间

{ c = A[i];count = 1;}

复杂度T（n）=O（k）。要求先给出算法思想，再写出相应代码。

if ( count>0 ) for (i=count=0; i

if ( A[i] = = c ) count++;

if ( count> n/2 ) return c; / / 确认候选主元素

else return -1; / / 不存在主元素 }

…………….……………..装……………………订………………..线…………….…………….. 计算机与信息 学院 第六部分 算法题

信息工程、计科 专业 数据结构 课程 共 20 页，第 20页，共印刷 份, — 年 月 日 考试，任课教师 5. 给定一棵用二叉链表表示的二叉树，每个结点都有2个指针（lchild,rchild)，分别指向其左、

右孩子结点，该二叉树的根结点指针为t，试编写一个基于中序遍历的非递归算法函数，求二叉树的叶子结点数目。

6. 假设二叉树采用二叉链表存储，根结点的指针为root ，按中序遍历时输出的结点顺序为a1，

a2，?an。试编写一算法求输出中序序列的逆序an，?，a2,a1序列。

1) 描述算法的基本思想。 2) 写出二叉链表的结点定义。

3) 根据算法的基本思想，采用程序设计语言C 描述算法，关键之处请给简要注释。

7. 假设二叉树T 采用二叉链存储结构，编写程序，求二叉树 T 的宽度(即具有结点数最多的那

一层上的结点个数)。写出算法思想。

第七部分 解答题

1. 试写出将S结点插入到双向链表P结点之前的语句序列，结点结构为：

prior data S->priou=P->priou; P->priou=S; S->next=P;

P->priou->next=S;

next 1. 统计一棵二叉树的叶子结点的个数

// 求二叉树中叶子结点的数目

Status POLeafNodeNum(int& i,BiTree& T) { if(T) {

if(!T->lchild && !T->rchild) i++;

POLeafNodeNum(i,T->lchild); POLeafNodeNum(i,T->rchild);} return OK;}

2. 统计一棵二叉树的度为2的结点个数 int Degrees2(BinTreeNode *t) { if (!t) return 0;

if(t->leftChild && t->rightChild)

return 1+Degrees2(t->leftChild)+Degrees2(t->rightChild); }

3. 统计一棵二叉树的深度

int Height(btre bt)//求二叉树bt 的深度 {int hl,hr;

if (bt==null) return(0);

else {hl=Height(bt->lch); hr=Height(bt->rch); if(hl>hr) return (hl+1); else return(hr+1); } }

4. 创建一棵二叉树

BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt;

scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0)

{bt=(BiNode *)malloc(sizeof(BiNode));

bt->data=x; bt->lchild=creat(); bt->rchild=creat(); }

else error(“输入错误”)； return(bt); }//结束 BiTree

本文来源：https://www.bwwdw.com/article/irfp.html