…………….……………..装……………………订………………..线………
…….……………..
阜阳师范学院 2013 ——
2014 学年度第 二 学期复习题
计算机与信息
学院 信息工程、计科
专业 数据结构 课程，共 20 页， 第1页，共印刷
份,
年 月 日
考试，任课教师
拟题 学号
第一部分 选择题
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 ．数据的逻辑结构
C ．数据的存储结构
D ．数据元素
4.L 是一个带头结点的空单向循环链表，若要向L 中插入一个由指针p 指向的结点，则执行（ ）。 A.L=p; p->next=L; B. L->next=p; p->next=L; 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. 各自的尾结点
C. 各自的第一个元素结点。
D.一个表的头结点，另一个表的尾结点
8.从逻辑上来分，数据结构可以分为（ ）两大类。
A. 动态结构、静态结构
B.顺序结构、链式结构
C. 线性结构、非线性结构
D.初等结构、构造型结构 9.算法分析的两个主要方面是：（ ）
A ． 空间复杂性和时间复杂性 B.正确性和简明性 C ． 可读性和文档性 D.数据复杂性和程序复杂性 10.计算机算法指的是：（ ）
A.计算方法
B.排序方法
C.解决问题的有限运算序列
D.调度方法
11.一个顺序表由（a 0,a 1,a 2,…a n-1）n 个元素构成，a 0存储地址是100，每个元素的长度为2，则a 4元素的地址是（ ）
A.110
B.108
C.100
D.120
12.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元
素。 A.8 B.63.5 C.63 D.7 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 ．单循环链表。
班 姓名
级
学院
…………….……………..装……………………订………………..线…………….……………..
计算机与信息 学院 信息工程、计科 专业 数据结构
课程 共 20 页，第 2 页，共印刷 份, 年 月 日
考试，任课教师 18.与单链表相比，双向链表的优点之一是（ ）
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 所指向的新结点，其修改指针的操作是（ ）。
A ．p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B ．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C ．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D ．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
21.以下说法错误的是（ ）。
A ．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
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)=2008n 3+8n 2+96000，g(n)=8n 3+8n+2008 和h(n)=8888nlogn+3n 2，下列陈述中不成立的是（ ） A ．f(n)是0(g(n))
B ．g(n)是0(f(n))
C ．h(n)是0(nlogn)
D ．h(n)是0(n 2)
25.指针p 、q 和r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的
程序 段是（ ）
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.用头指针表示的单循环链表
C.用尾指针表示的单循环链表
D.单链表
27.设某线性表有n 个元素，以下操作中，（ ）在顺序表上实现比在链表上实现效率更高。
A.输出第i 个元素（1<=i<=n ）
B.交换第1个元素和第二个元素的值
C.顺序输出这n 个元素的值
D.输出与给定值x 相等的元素在线性表中的序号
28.算法的时间复杂度是指（ ） A ．算法执行的绝对时间
B ．随着问题规模n 的增大，算法执行时间的增长趋势。
C ．算法中执行语句的条数
D ．获得算法执行时间的复杂程度。
29.数据结构是指（ ）
A ．数据的基本单位
B ．性质相同的数据元素的集合
C ．相互之间存在一种或多种特定关系的数据元素集合
D ．描述客观事物且由计算处理的数值、字符等符号的总称 30.已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n 的降序链表，则最坏情况下的时间复杂度是（ ） 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,则下列序列中，是栈的合法输出序列的是（）。
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.一个递归算法必须包括（ ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D.终止条件和迭代部分 34.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A ．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
35.用带头结点的单链表存储队列时，在进行删除运算时（）。
A. 仅修改头指针
B. 可能要修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
36.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
A ．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改
D. 队头,队尾指针都可能要修改
37.循环队列A[0..m-1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是( )。
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front 38.栈和队列的共同点是（）。
A. 都是先进先出
B. 都是先进后出
…………….……………..装……………………订………………..线…………….……………..
计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 3 页，共印刷 份, 年 月 日 — 考试，任课教师
C. 只允许在端点处插入和删除元素
D. 没有共同点 39.栈的插入和删除操作在（）进行。
A ．栈顶
B ．栈底
C ．任意位置
D ．指定位置
40.元素a,b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（）
A. 3
B. 4
C. 5
D.6 41.已知循环队列存储在一维数组A[0..n-l] 中，且队列非空时，front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第l 个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是（）
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 的容量至少是（）
A. 1
B. 2
C. 3
D. 4 43.若元素a 、b 、c 、d 、e 、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是（）
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 依次入此队列后再进行出队操作，则不可能得到的出队序列是（）
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 的值分别为（）。 A. 1，5 B. 2，4 C. 4，2 D. 5，1 46.最不适合用作链队的链表（ ）
A ．只带队头指针的非循环双链表
B ．只带队头指针的循环双链表
C ．只带队尾指针的循环双链表
D ．只带队尾指针的循环单链表
47.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50 个元素，则队列的尾指针值为（）
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.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为() A ．前序遍历 B ．后序遍历 C.中序遍历 D.层次遍历 50.在一棵高度为k 的满二叉树中，结点总数为（）
A ．2k-1
B ．2k
C ．2k -1
D ．?log2k
?+1
51. 若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为（）。
A ．i
B ．n-i
C ．n-i+1
D ．不确定
52.链式栈结点为：(data,link)，top 指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x
中,则应执行操作（）。 A ．x=top->data;top=top->link ； B ．top=top->link;x=top->link ； C ．x=top;top=top->link ；
D ．x=top->link ；
53.循环队列存储在数组A[0...m]中，则入队时的操作为（）。
A. rear=rear+1
B. rear=(rear+1)%(m-1)
C. rear=(rear+1)%m
D. rear=(rear+1)%(m+1)
54.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
55.若一棵二叉树的前序遍历序列和后序遍历序列分别是1，2，3，4和4，3，2，1，同该二叉树的中序遍历列不会是（）
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 可能具有的关系是（）
I ．父子关系 II.兄弟关系 III.u 的父结点与v 的父结点是兄弟关系
A.只有II
B.I 和II
C.I 和III
D.I 、II 和III
57.已知一棵有2011个结点的树，其叶结点的个数为116，该树对应的二叉树中无右孩子的结点个数是( )
A.115
B.116
C.1895
D.1896 58.对n(n>=2)个权值均不相同的字符构成赫夫曼树,关于该树的叙述中,错误的是（）
A ．该树一定是一棵完全二叉树
B ．树中一定没有度为1 的结点
C ．树中两个权值最小的结点一定是兄弟结点
D ．树中任一非叶结点的权值一定不小于下一层任一结点的权值 59.一棵完全二叉树的结点总数为28，则该完全二叉树的深度为（）。
A.4
B.)5
C.6
D.7
60.一棵树高为K 的完全二叉树至少有（）个结点
A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2
k
61. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
A ．CBEFDA
B ． FEDCBA
C ． CBEDFA
D ．不定
62. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）
A ．所有的结点均无左孩子
B ．所有的结点均无右孩子
…………….……………..装……………………订………………..线…………….……………..
C ．只有一个叶子结点
D ．是任意一棵二叉树 63.n 个结点的线索二叉树上含有的线索数为（） A ．2n B ．n －l C ．n ＋l D ．n 64.在一非空二叉树的中序遍历序列中,根结点的右边( )
A.只有右子树上的所有结点
B.只有右子树上的部分结点
C.只有左子树上的部分结点
D.只有左子树上的所有结点
65.设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对
应的二叉树根结点的右子树上的结点个数是（）。
A ．M1
B ．M1+M2
C ．M3
D ．M2+M3
66.在由4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，
当把森林转换成二叉树后，对应的二叉树中根节点的左子树中结点个数为（）。
A ． 64
B ．29
C ．30
D ．4
67.在一棵度数为4 的树T 中,若有20 个度为4 的结点,10 个度为3 的结点,1 个度为2 的结
点,10 个度为1 的结点,则树T 的叶结点个数是（）
A.41
B.82
C.113
D.122
68.已知一棵完全二叉树的第6 层（设根为第1 层）有8 个叶结点，则该完全二叉树的结点个数
最多是（）
A ．39 B.52 C.111 D.119
69．若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（）
A ．257 B.258 C.384 D.385
70.层次遍历一个完全二叉树的序列是：abcdefghij,则先序遍历序列为()
A.abcdefghij
B.abdhiejcfg
C.acfgbejdhi
D.acbgfedjih
71.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（）。
A ． 不发生改变
B ．发生改变
C ．不能确定
D ．以上都不对
72.在下述论述中，正确的是()。
①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换； ④深度为K 的顺序二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③
B ．②③④
C ．②④
D ．①④
73.二叉树先序遍历和中序遍历如下：先序序列：EFHIGJK 中序序列：HFIEJKG
该二叉树根的右子树的根是（） A.E B.F C.G D.H
74.若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（）。
A ．X 的双亲
B ．X 的右子树中最左的结点
C ．X 的左子树中最右结点
D ．X 的左子树中最右叶结点 75.引入二叉线索树的目的是（）。
A ．加快查找结点的前驱或后继的速度
B ．为了能在二叉树中方便的进行插入与删除
C ．为了能方便的找到双亲
D ．使二叉树的遍历结果唯一 76.设F 是一个森林，B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针域为空
的结点有（）个。 A ． n-1 B ．n C ． n+1 D ． n+2
77.将一棵有 50 个结点的完全二叉树按层编号，则对编号为 25 的结点 x ，该结
点 ( )。 A ．无左、右孩子 B ．有左孩子，无右孩子 C ．有右孩子，无左孩子 D ．有左、右孩子 78.在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 79.具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余() 个指针域为空。
A. 50
B. 99
C. 100
D.101
80.由权值分别为4,8,6,3,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A.24 B.36 C.49 D.59
81.根据使用频率为5 个字符设计的哈夫曼编码不可能是( ) 。
A. 000, 001 , 010, 011 , 1
B. 0000, 0001 , 001 , 01 , 1
C. 000, 001 , 01 , 10, 11
D. 00, 100, 101 , 110, 111
82.一个栈的入栈序列为1, 2,3,…,n ，其出栈序列是p 1,p 2,p 3，…p n 。若p 2=3，则p 3可能取值的
个数是(C )
A. n -3
B. n -2
C. n -1
D. 无法确定
83.已知三叉树T 中6 个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是(B)
A. 27
B. 46
C. 54
D. 56 84.若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ A ） A. X 的父结点 B. 以Y 为根的子树的最左下结点 C. X 的左兄弟结点Y D. 以Y 为根的子树的最右下结点 85.设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1
B ．n(n-1)/2
C ． n(n+1)/2
D ．0
E ．n 2
86.一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1
B ．n
C ．n+1
D ．nlogn ； 87.要连通具有n 个顶点的有向图，至少需要（ ）条边。
A ．n-l
B ．n
C ．n+l
D ．2n
…………….……………..装……………………订………………..线…………….……………..
88．个结点的完全有向图含有边的数目（ ）。
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 ．AO
E 网 91.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A. O(n)
B. O(n+e)
C. O(n 2
) D. O(n 3
)
92.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）
93.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
94.对线性表进行二分查找时，要求线性表必须（ ）
A.以顺序方式存储
B.以顺序方式存储,且数据元素有序
C.以链接方式存储
D.以链接方式存储,且数据元素有序
95.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
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,则应作( ) 型调整以使其平衡。
A. LL
B. LR
C. RL
D. RR
97.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法
构造散列表，散列函数为H （key ）=key MOD 13,散列地址为1的链中有（）个记录。
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 ，杂凑)查找的说法正确的是( )
A ．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B ．除留余数法是所有哈希函数中最好的
C ．不存在特别好与坏的哈希函数，要视情况而定
D ．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
101.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共
四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A ．8 B ．3 C ．5 D ．9
102.已知关键序列5,8,12,19,28,20,15,22 是小根堆（最小堆），插入关键字3， 调整后得到的小根堆是（） A ．3,5,12,8,28,20,15,22,19 B. 3,5,12,19,20,15,22,8,28 C ．3,8,12,5,20,15,22,28,19
D. 3,12,5,8,28,20,15,22,19
103.若数据元素序列11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第 二趟排序后的结果，则该排序算法只能是（） A ．起泡排序
B.插入排序
C.选择排序
D.二路归并排序
104.对下图进行拓扑排序,可以得到不同的拓扑序列的个数是()
A.4
B.3
C.2
D.1
A ．0 1 3 2 B. 0 2 3 1
C. 0 3 2 1
D. 0 1 2 3
A ．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
…………….……………..装……………………订………………..线…………….……………..
105.已知一个长度为16 的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多的是()
A.4
B.5
C.6
D.7
106.采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是()
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.冒泡排序法
B.希尔排序法
C.归并排序法
D.基数排序法
108.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）
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.下列关于图的叙述中，正确的是（）。
I ．回路是简单路径
II ．存储稀疏图，用邻接矩阵比邻接表更省空间 III ．若有向图中存在拓扑序列，则该图不存在回路 A ．仅II B ．仅I 、II C ．仅III D ．仅I 、III 110.判断有向图是否有回路，除了可以用拓扑排序外，还可以用（ ）。
A ．求关键路径的方法
B ．广度优先遍历算法
C ．求最短路径的方法
D ．深度优先遍历算法
111.任何一个带权无向连通图的最小生成树是（ C ）
A ．一定是唯一的
B ．一定不唯一的
C ．有可能不唯一的
D ．有可能不存在的
112.为提高散列（HASH ）表的查找效率，可以采取的正确措施是（D ） I ．增大装填（载）因子
II ．设计冲突（碰撞）少的散列函数
III ．处理冲突（碰撞）时避免产生聚集（堆积）现象 A ．仅I B ．仅II C ．仅I 、II D ．仅II 、III 113.为实现快速排序算法，待排序序列宜采用的存储方式是（）
A ．顺序存储 B.散列存储 C.链式存储 D.索引存储
114.已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）
A ．1 B.2 C.4 D. 5 115.某内排序方法的稳定性是指( )。
A ．该排序算法不允许有相同的关键字记录
B ．该排序算法允许有相同的关键字记录
C ．平均时间为0（n log n ）的排序方法
D ．以上都不对 116.下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 堆积 117.下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，冒泡排序
118.若需在O(nlog 2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序 119.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。
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. 选择
B. 冒泡
C. 快速
D. 插入
121.下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell 排序 C. 堆排序 D.冒泡排序
…………….……………..装……………………订………………..线…………….……………..
122.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
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 ）的是( ) 。
A ．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 124.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。
A ． 冒泡 B. 希尔 C. 快速 D. 堆
125.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。
A ．起泡排序
B ．快速排列
C ．Shell 排序
D ．堆排序
126.如果在构造哈希表时采用链地址法解决冲突，且啥希函数为H(key)=key MOD 8则需要建造的链表数目是（ ）
A ．6
B ．5
C ．8
D ．9
127.下列因素中，影响排序算法稳定性关键因素是（B ）。
I ．待排元素个数的多少
II.排序过程中是否发生了不相邻元素的交换 III.是否有关键码相同的元素 IV.排序算法是否采用递归方式实现
A ．仅I
B ．仅II
C ．I 和III
D ．I 和IV
128.用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。
A ． 94,32,40,90,80,46,21,69
B ． 32,40,21,46,69,94,90,80
C ． 21,32,46,40,80,69,90,94
D ． 90,69,80,46,21,32,94,40
129.对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l ，4，8，20，9，7}则该次采用的增量是 ( ) A. l B. 4 C. 3 D. 2 130.下列四个序列中，哪一个是堆（）。
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 ．顺序
B ．二分法
C ．顺序，也能二分法
D ．随机
132.堆排序是一种( )排序。
Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并
133.假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要进行多少次探测？( )
A ．k-1次 B. k 次 C. k+1次 D. k （k+1）/2次 134.下列二叉排序树中，满足平衡二叉树定义的是（）
135.下列关于无向连通图特性的叙述中，正确的是（ ）
I ．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1
A.只有I
B. 只有II
C.I 和II
D.I 和III
136.在下列所示的平衡二叉树中插入关键字48 后得到一棵新平衡二叉树,在新平衡二叉 树中,关键字37 所在结点的左、右子结点中保存的关键字分别是() A.13,48
B.24,48
C.24,53
D.24,90
137.用序列｛12，13，11，18，60，15，7，18，25，84｝构建初始堆，必须从关键字为（ ）的结点开始。
A.84
B.12
C.60
D.15
138.关键路径是（ ） A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
C.从源点到汇点的最长的回路
D.从源点到汇点的最短的回路
…………….……………..装……………………订………………..线…………….……………..
139.在平衡二叉排序树中，每个结点（ ） A.左子树结点个数和右子树结点个数相差不超过1 B.平衡因子为0
C.左子树度数和右子树度数相差不超过1
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
C.20，8，16，29，24，22，4
D.4，8，16，20，24，29
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 中有弧
D.G 中有一条从Vj 到Vi 的路径
147.具有6个顶点的无向图，当有（ ）条边时能确保是一个连通图。 A.8
B.9
C.10
D.11。
148.一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。 A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图
149.若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则平衡二叉树的结点总数为 A.10
B.20
C.32
D.33
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 2
) D.O(n 3
)
153.已知一个图中包含k 个连通分量。如果按照深度优先搜索算法（DFS ）遍历所有顶点，则必须调用该算法（ ）次 A.1
B. k-1
C. k
D.k+1
154.在最好和最坏情况下的时间复杂度均为O(nlogn) 且稳定的排序方法是( )。 A.快速排序 B. 堆排序 C. 归并排序 D. 基数排序
155.索引顺序表是将表分成若干子表(或称块)据此建立索引表，并要求关键字( )。 A. 块内有序，块间有序
B.块内无序，块间有序
C.块内有序，块间无序。
D.块内无序，块间无序
156.hash 函数为模运算，下面哪个值作为模数更好?（ ） A.1000 B. 1024 C. 972 D. 997
157.若从二叉树的任意结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（ ）
A.二叉排序树
B.完全二叉树
C. 堆
D. 平衡二叉树 158.在二叉排序树中，数值最小的结点是（ ） A.最左结点 B.最右结点 C.根结点
D.不确定
159.折半插入排序是对直接插入排序的改进，它着眼于减少（ ）
A.移动元素的次数
B.排序的趟数
…………….……………..装……………………订………………..线…………….……………..
C.与关键字比较的次数
D.空间复杂度
160.在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D ）位置上。 A ．n/2
B ．n/2 -1
C ．1
D ．n/2 +2
161.若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0 的分支结点的个数是（ D ） A. 0
B. 1
C. 2
D. 3
162.在任意一棵非空二叉排序树T 1 中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2 形成二叉排序树T 3。下列关于T 1 与T 3 的叙述中，正确的是（ C ） I. 若v 是T 1 的叶结点，则T 1 与T 3 不同 II. 若v 是T 1 的叶结点，则T 1 与T 3 相同 III. 若v 不是T 1 的叶结点，则T 1 与T 3 不同 IV. 若v 不是T 1 的叶结点，则T 1 与T 3 相同
A. 仅I 、III
B. 仅I 、IV
C. 仅II 、III
D. 仅II 、IV 163.设图的邻接矩阵A 如下所示。各顶点的度依次是（ C ）
A. 1，2，1，2
B. 2，2，1，1
C. 3，4，2，3
D. 4，4，2，2
164.若对如下无向图进行遍历，则下列选项中，不．是广度优先遍历序列的是（ D ） A. h ，c ，a ，b ，d ，e ，g ，f B. e ，a ，f ，g ，b ，h ，c ，d C. d ，b ，c ，a ，h ，e ，f ，g
D. a ，b ，c ，d ，h ，e ，f ，g
165.下列 AOE 网表示一项包含 8个活动的工程。通过同时加快若干进度可以缩短整个工程的工
期。下列选项中，加快其进度就可以缩短程是（ C ） A.c 和e B. d 和e C.f 和d
D. f 和
h
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
D. 110，120，911，122，114，007，119
第二部分 填空题
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= ________; }
}
…………….……………..装……………………订………………..线…………….……………..
5.数据的链式存储结构的特点是借助________表示数据元素之间的逻辑关系。
6.在如图所示的链表中，若在指针p 所指的结点之后插入数据域值相继为a 和b 的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。
7.栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
8. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 9.如果结点A 有 3个兄弟，而且B 是A 的双亲，则B 的度是_4_。 10.含4个度为2的结点和5个叶子结点的二叉树，可有__0至多____个度为1的结点。 11.设n 0为哈夫曼树的叶子结点数目，则该哈夫曼树共有___2n 0-1___个结点。
12.以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt 为根结点的指针*/ {int hl,hr; if (bt==NULL) return((1)___);
hl=depth(bt->lchild); hr=depth(bt->rchild);
if((2)___) (3)_____；
return(hr+1);13.一棵深度为6的满二叉树有 31 个分支结点和 23232 个叶子。
14.将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为0，则编号为50 的结点的右孩子编号为 。 15.在计算机内实现递归算法时所需的辅助数据结构是 16.若要在中序线索二叉树中找到左子树中序序列的最后一个结点， 则需要找其右指针指向 的结点。
17.设根的层次为1，则有64 个结点的完全二叉树的深度为
18.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必定也是该子树的_________序列中的最后一个结点。 19.有向图G 用邻接表矩阵存储，其第i 行的所有元素之和等于顶点i 的 20.n 个顶点e 条边的图，若采用邻接矩阵存储，则空间复杂度为 。 21.n 个顶点e 条边的图，若采用邻接表存储，则空间复杂度为 。 22.设有一稀疏图G ，则G 采用 存储较省空间。 23.设有一稠密图G ，则G 采用 存储较省空间。
24.图的逆邻接表存储结构只适用于 图。
25.含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过 。
26.用普里姆(Prim)算法求具有n 个顶点e 条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。
27.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。
28.在直接插入排序、希尔排序、直接选择排序、堆排序、快速排序和基数排序中,需要内存量最
大的是 。 29.折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。 30.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序，则选用 。
31.大多数排序算法都有两个基本的操作： 和 。
32.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找关键码值20，需做的关键码比较次数为_ _. 33.已知二叉排序树的左右子树均不为空，则_ _ _上所有结点的值均小于它的根结点值，__ ____
上所有结点的值均大于它的根结点的值。 34.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__ _趟，写出第一趟结束后，数组中数据的排列次序_____ _。 35.具有10个顶点的无向图，边的总数最多为_ ___。 36.G 是一个非连通无向图，共有28条边，则该图至少有 _个顶点。 37.在有n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__ __条弧 38.在有n 个顶点的有向图中，每个顶点的度最大可达_ _____。
39.设G 为具有N 个顶点的无向连通图，则G 中至少有 条边。 40.N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有__ ______个非零元素。 41.求图的最小生成树有两种算法，_ ____算法适合于求稀疏图的最小生成树。 42.在AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为__ ____。 43.无向图中的一个极大连通子图称为它的一个________。 44._____________排序不需要进行记录关键字间的比较。
45.已知一组数据( 15 ，19, 17, 8, 20，25,7) , 用堆排序的筛选方法建立了初始小根:堆后，
则最后一个结点值为
…………….……………..装……………………订………………..线…………….……………..
第三部分 判断题
1.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。( )
2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高.( )
3.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻( )
4.循环链表不是线性表.( )
5.算法的优劣与算法描述语言无关，但与所用计算机有关。( )
6.线性表的特点是每个元素都有一个前驱和一个后继。( )
7.若二叉树用二叉链表作存贮结构，则在n 个结点的二叉树链表中只有n —1个非空指针域。( ) 8二叉树中每个结点的两棵子树是有序的.( )
9.由二叉树的先序遍历序列和后序遍历序列并不能唯一确定这棵树，因为不知道树的根结点是哪一个。( )
10.将一棵树转成二叉树，根结点没有左子树( ) 11.所有二叉树的度均为2。（）
12.满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。（ ）
13.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ） 14.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ） 15.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1 （ ） 16.二叉树是度为2的有序树。（ ）
17.采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。（ ） 18.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
19.在二叉树的第i 层上至少有2i-1
个结点(i>=1)。（ ）
20.将一棵树转成二叉树，根结点没有右子树。（ ） 21.深度为K 的二叉树中结点总数≤2k
-1。（ ） 22.度为二的树就是二叉树。（ ）
23.若散列表的负载因子α<1，则可避免碰撞的产生。( )
24.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。.( )
25.顺序查找法适用于存储结构为顺序或链接存储的线性表。( ) 26.在二叉树排序树中插入一个新结点，总是插入到叶结点下面。（ ） 27.完全二叉树肯定是平衡二叉树。（ ）
28.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。（ ）
29.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 30.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
31.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog 2n
),所以快速排序比冒泡排序算法效率更高。 （ ）
32.无环有向图才能进行拓扑排序。（ ）
33.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 34.有n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ）
35.十字链表是无向图的一种存储结构。（ ） 36.强连通分量是无向图的极大强连通子图。（ ） 37.连通分量指的是有向图中的极大连通子图。（ ） 38.邻接多重表是无向图和有向图的链式存储结构。（ ）
39.在n 个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ） 40.不同的求最小生成树的方法最后得到的生成树是相同的.（ ） 41.AOV 网的含义是以边表示活动的网。（ ）
42.对一个AOV 网，从源点到终点的路径最长的路径称作关键路径。（ ）
43.在表示某工程的AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。
（ ）
第四部分 应用题
1. 设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。
（2）将这棵二叉树转换成对应的树（或森林）。
…………….……………..装……………………订………………..线…………….……………..
2. 已知一棵二叉排序树的前序遍历序列为25，10,5,12,18,35,46,40,请回答下列问题： (1)画出此二叉排序树(5 分)
(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。
3. 有5 个元素，其入栈次序为：A ，B ，C ，D ，E ，在各种可能的出栈次序中，以元素C ，D 最先
出栈（即C 第一个且D 第二个出栈）的次序有哪几个？CDEBA 、CDBEA 、CDBAE
4. 对于给定的5个实数W={8，5，13，2，6}，试构造Huffman 树；并求出该树的最小带权路径
长度并求各结点的Huffman 编码。
5. 设有一棵树，如右图所示： 回答下列问题：
（1）哪个是根结点？哪些是叶子结点？ （2）树的度数和树的深度是多少？ （3）写出结点F 的双亲、祖先、孩子？
（4）写出结点B 的子孙、兄弟和结点B 所在的层次？
6. 将下面的森林变换成二叉树。
7. 画出下列二叉树所对应的中序线索二叉树。
8. 假设某密文仅有8 个字母C1，C2，.....C7，C8 组成，各个字母在电文中出现 的频率分别为5，25，3，6，10，11，36，4，试回答以下问题： （1）构造出相对应的哈夫曼树。 （2）写出该8 个字母的哈夫曼编码。 （3）试计算该哈夫曼树的带权路径长度。
…………….……………..装……………………订………………..线…………….……………..
9. 二叉树以二叉链表的方式 存储，设一棵二叉树有n 个结点，问（1）该二叉链表中有几个指针域为空？为什么？（2）又设该二叉树有K 片叶子，这棵二叉树有多少个结点既有左孩子又有右孩子？为什么？
10. 假设一棵二叉树的层次序列为ABCDEFGHIJ 中序序列DBGEHJACIF 要求： 1）画出该二叉树。
2）画出该二叉树对应的森林。 3）给出对该森林进行后根遍历的序列。 4）画出该二叉树的中序线索二叉树。
11. 有一份电文中共使用五个字符：a 、b 、c 、d 、e,它们的出现频率依次为 8、14、10、4、18，
请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。
12. 对电文“gogoesgoodgoods ”进行哈夫曼编码，请完成下列任务：
（1）所构成的哈夫曼树的总节点个数为多少，并计算其带权路径氏度。 （2）写出电文中所含字符的哈夫曼编码。
（3）写出该段电文的哈夫曼编码，并求其总编码长度
13. 已知在一电文中只使用了8个字符A ，B,C,D,E,F,G,H ，其频率分别为( 36,10,18,8,2,16,4,
12 )画出哈夫曼树，并写出每个字符对应的哈夫曼编码。
14.设G=(V,E)以邻接表存储，如图所示，试从顶点1出发，画出图的深度优先和广度优先生成树。
15.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1） 画出描述折半查找过程的判定树； （2） 若查找元素54，需依次与哪些元素比较？ （3） 若查找元素90，需依次与哪些元素比较？
（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解：（1） 先画出判定树如下（注：mid=?(1+12)/2?=6）：
(2) 查找元素54，需依次与30, 63, 42, 54 元素比较；(3) 查找元素90，需依次与30, 63,87, 95元素比较；（4） 求ASL 之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL ＝（17＋20） /12＝37/12≈3.08
…………….……………..装……………………订………………..线…………….……………..
16.设哈希（Hash ）表的地址范围为0～17，哈希函数为：H （K ）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash 表，试回答下列问题：
（1） 画出哈希表的示意图；
（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？
（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，ASL=1/11（6＋2＋3×3）＝17/11≈1.55
17.将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中,散列表的存储空间是一个下标从0 开始的一个一维数组散列,函数为:H(key)=(key ×3)MOD 7,处理冲突采用线性探测再散列法,要求装载因子为0.7.问: (1)请画出所构造的散列表.
(2)分别计算等概率情况下,查找成功和查找不成功的平均查找长度.
18. 设散列函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合
{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL 。
19.给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。
20.已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，
试画出构造过程）。
21.下图是带权的有向图G 的邻接表表示法，求：
（1）．以结点V1出发深度遍历图G 所得的结点序列； （2）．以结点V1出发广度遍历图G 所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。
…………….……………..装……………………订………………..线…………….……………..
22.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列；
(1) 希尔排序（第一趟排序的增量为5） (2) 快速排序（选第一个记录为枢轴（分隔））
(1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 （ D=5） (2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,18
23.排序有各种方法，如直接插入排序，冒泡排序，快速排序，简单选择排序，堆排序，二路归并排序，基数排序等。设一数组中原有数据如下：150，110，35，40，45，85，80。下面是一组由不同排序方法进行第一趟排序后的结果。
方法一排序的结果为：80，110，35，40，45，85，150 方法二排序的结果为：110，35，40，45，85，80，150 方法三排序的结果为：110，150，35，40，45，85，80 方法四排序的结果为：35，110，150，40，45，85，80 请问：
（1）方法一，方法二，方法三，方法四分别是什么排序方法？
（2）方法一，方法二，方法三，方法四在第一趟排序过程中发生的比较次数分别是多少？ （3）方法一，方法二，方法三，方法四中哪些是稳定的，哪些是不稳定的？
（4）假设待排序表长度为n ，则方法一，方法二，方法三，方法四的平均时间复杂度分别是多少？
设一信号灯，产生的颜色有（RED ，GREEN ，BLUE ，YELLOW ，BLACK ，BROWN ，WHITE ）
出现的概率分别为（0.04，0.12，0.3，0.14，0.25，0.1，0.05），试用二进制对其编码，使产生的数
据量最少。
24.若有如下无向图G
1.试画出G 的邻接表表示，要求邻接表中的表结点按顶点序号从小到大排列。
2.根据你所给出的邻接表，分别给出从顶点A 出发的深度优先搜索序列和深度优先搜索生成
树。
25.输入关键字序列｛16,3,7,11,9,26,18,14,15，12｝，给出构造一棵平衡二叉树的步骤。
26.已知哈希函数H(k)=2*k mod 11，用开放地址法处理冲突：
H i (k) =(H(k)+d i ) mod 11 i=l, 2,…；其中d 1=1, d i+1=(7d i +3) mod ll (i>=l )。
试在0～10的哈希地址空间中对关键字序列(6，8，10，17,20,23,53，41,54,57)
构造哈希表。
…………….……………..装……………………订………………..线…………….……………..
27.已知世界6 大城市：北京(B)、纽约(N) 、巴黎（p ）、伦敦(L) 、东京(T)、墨西哥城（M)。试在下表给出的交通网中确定最小生成树，并说明所使用的方法和时间复杂度。 表：世界6 大城市交通里程网络表(单位：1OOkm)
28.已知数据序列为(36，74，8，50，18，6，40，30)，给出建立二叉排序树的过程示意图，再给出删除74，8后的二叉排序树。
29.对下面的有向图。
1) 给出每个顶点的入度和出度 2) 画出邻接链表 3) 求所有可能的拓扑序
第五部分 算法设计题
1. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 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->data
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)
…………….……………..装……………………订………………..线…………….……………..
4. 假设该链表只给出了头指针list 链表中倒数第K 位置的结点（K 为正整数），若查找成功，算法输出该结点 data 域的值，并返回1，否则只返回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
{ s=r; q=p; } r=p;p=p->link;} if(q!=r) then { if (q==list) then list=q->link;
else s->link=q->link; r->link=q; q->link=NULL; } } 6. 若已知非空线性链表第一个结点的指针为list ，请 写一个算法，将该链表中数据域值最小的
那个结点移到链表的最前端。
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; } }
7. 已知一个带有表头结点的单链表，头指针为L ，请用一个尽可能高效的算法实现，在非头结
点p 所指元素前，插入元素e,并分析算法的时间复杂度。
时间复杂度O(n) 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;
typedef struct node {datatype data; struct node *next;}lklist;
void delredundant(lklist *&head) { lklist *p,*q,*s;
for(p=head;p!=0;p=p->next)
{ for(q=p->next,s=q;q!=0; )
if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}
else {s=q,q=q->next;}
} }
10. 编写算法，判断带头结点的双向循环链表L 是否对称。对称是指：设各元素值a 1,a 2,...,a n ,
则有a i =a n-i+1 ，即指：a 1= a n ，a 2= a n-1 。。。。。。
。 结点结构为：
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; }
…………….……………..装……………………订………………..线…………….……………..
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；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={ "do"，"for"，" repeat"，" while"}，各元素的查 找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将S 保存在一个长度为4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。请回答：
（1）若采用顺序存储结构保存S ，且要求平均查找长度更短，则元素应如何排列？应使用 何种查找方法？查找成功时的平均查找长度是多少？
（2）若采用链式存储结构保存S ，且要求平均查找长度更短，则元素应如何排列？应使用 何种查找方法？查找成功时的平均查找长度是多少？
…………….……………..装……………………订………………..线…………….……………..
20. 已知一个整数序列A= (a 0, a 1,…，a n-1) ，其中0≤a i ＜ n(0 ≤ i ＜ n) 。若存在a p =a p2 =…=a pm =x 且m ＞n/2(0 ≤p k A 中的n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A 的主元素。 若存在主元素，则输出该元素；否则输出-1。要求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或C++或Java 语言描述算法，关键之处给出注释。 （3 （1）算法的策略是从前向后扫描数组元素，标记出一个可能成为 主元素 的Num 。然 后重新计数 ，确认 NumNum 是否主元素。 算法可分为以下两步 ： ① 选取候的主元素 ：依次扫描所给数 组中的每个整，将第一遇到Nu m 保存 到 c 中，记录 Nu m 的出现次数为 的出现次数为 1； 若遇到的下一个整数仍等于 NumNum ，则计数加 1， 否则计数减 1；当计数减到 0时，将遇到 的 下一个整数保存c 中，计数重新记为 中，计数重新记为 1， 开始新一轮计数，即从当前位置重 复上述过程直到扫描完全部组元素。 ② 判断 c 中元素 是否真正的主中元素 是否真正的主：再 次扫描该数组，统计 c 中元素出现的次数，若 中元素出现的次数，若 大于 n/2 ，则为主元素 ；否则，序列中不存在主元素。 （2）算法实现：（7分） int Majority(int A[], int n) {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) / / 处理不是候选主元素的情况 count--;else / / 更换候选主元素，重新计数 { c = A[i];count = 1;} if ( count>0 ) for (i=count=0; i if ( A[i] = = c ) count++; if ( count> n/2 ) return c; / / 确认候选主元素 else return -1; / / 不存在主元素 } 21.设二叉排序树bt 以二叉链表为存储结构，试设计算法删除二叉排序树bt 中值最大的结点。 Status del_max(BiTree &bt){ --------1分 //删除二叉排序树bt 中值最大结点 if (!bt) return ERROR; //空树 p = bt; if (bt->rchild == NULL){ //根无右子树 --------2分 bt = bt->lchild; p->lchild = NULL;//此语句可不要 free(p); } else{ while(p->rchild != NULL){//p 移至最右下结点 q = p; p = p->rchild;} if(p->lchild != NULL)//有左子树 --------5分 q->rchild = p->lchild; else q->rchild = NULL;//无左子树 free(p); } }//del_max 22.假设无向图G ，采用邻接表存储，编写程序，判断图G 是否是连通图，若是连通图返回1，否 则返回O 。 写出算法思想。 23.设二叉排序树中的结点值为整型，最大值为MAX ， 给出任意整型值x ( x <=MAX)， 编写程 序， 求二叉排序树中大于x 的最小一个数。（提示x 不一定在树中） 24.设二叉排序树T 的key 值为整数，高度为k ，对任意给定的整数x ，查找元素值小于x 且最 接近x 的结点并返回结点指针，如该结点不存在则返回指针为空，要求用非递归算法实现且时间 复杂度T （n ）=O （k ）。要求先给出算法思想，再写出相应代码。 …………….……………..装……………………订………………..线…………….…………….. 第六部分 算法题 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 5. 给定一棵用二叉链表表示的二叉树，每个结点都有2个指针（lchild,rchild)，分别指向其左、 右孩子结点，该二叉树的根结点指针为t ，试编写一个基于中序遍历的非递归算法函数，求二叉树的叶子结点数目。 6. 假设二叉树采用二叉链表存储，根结点的指针为root ，按中序遍历时输出的结点顺序为a1， a2，…an 。试编写一算法求输出中序序列的逆序an ，…，a2,a1序列。 1) 描述算法的基本思想。 2) 写出二叉链表的结点定义。 3) 根据算法的基本思想，采用程序设计语言C 描述算法，关键之处请给简要注释。 7. 假设二叉树T 采用二叉链存储结构，编写程序，求二叉树 T 的宽度(即具有结点数最多的那 一层上的结点个数)。写出算法思想。 第七部分 解答题 1. 试写出将S 结点插入到双向链表P 结点之前的语句序列，结点结构为： S->priou=P->priou; P->priou=S; S->next=P; P->priou->next=S; 数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系 4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（x ） 8、线性的数据结构可以顺序存储，也可以存储。非线性的数据结构只能存储。（x ） 9、栈和队列逻辑上都是线性表。（v ） 10、单链表从任何一个结点出发，都能访问到所有结点（v ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（x ） 12、快速排序是排序算法中最快的一种。（x ） 13、多维数组是向量的推广。（x） 14、一般树和二叉树的结点数目都可以为0。（v） 15、直接选择排序是一种不稳定的排序方法。（x ） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（v ） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（x ） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（x ） 19、堆栈在数据中的存储原则是先进先出。（x ） 20、队列在数据中的存储原则是后进先出。（x ） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（x ） 22、哈夫曼树一定是满二叉树。（x ） 23、程序是用计算机语言表述的算法。（v） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（v ） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（x ） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（v ） 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（v ） 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（C）。 for(i=0;i 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） 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） 9.对一组数据（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则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序数据结构考试试题及答案
数据结构试题库答案
数据结构试卷带答案
数据结构试题及答案(免费)
《数据结构》题库及答案
数据结构考试题库
数据结构试题集(包含答案 完整版)
数据结构试题及答案(10套最新)
数据结构考试题库含答案
数据结构试题及答案
2017年数据结构期末考试题及答案A
算法与数据结构题库与答案
数据结构试题及答案
数据结构期末考试题及标准答案
数据结构试题(含答案)
大数据结构试题集(含答案)
《数据结构》期末考试题及答案
相关主题
文本预览