徐州工程学院试卷
一、选择题（共15小题，每题2分，共计30分）
1. 算法分析的两个主要方面是。
A．数据复杂性和程序复杂性B．可读性和文档性
C．时间复杂度和空间复杂度D．正确性和简单性
2. 数据的四种存储结构是。
A．顺序存储结构、链接存储结构、索引存储结构和散列存储结构
B．线性存储结构、非线性存储结构、树型存储结构和图型存储结构
C．集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构
D．顺序存储结构、树型存储结构、图型存储结构和散列存储结构
3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
4. 在一个单链表中，若删除p所指结点的后续结点，则执行。
A．p->next=p->next->next; B．s->next=p->next;p->next=s;
C．p->next=p->next; D．p =p->next->next;
5. 4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态是：
不可能的出栈序列是。
A．a4，a3，a2，a1 B．a3，a2，a4，a1
C．a3，a1，a4，a2 D．a3，a4，a2，a1
6. 判定一个队列QU（最多元素为m0）为满队列的条件是。
A．QU->rear －QU->front = = m0 B．QU->rear －QU->front －1= = m0
C．QU->front = = QU->rear D．QU->front = = QU->rear+1
7. 设有一个二维数组A[10][15]，数组按行存放，假设A[0][0]存放位置在644,每个元素占一个空间，则A[4][5]
在位置。
A．672 B．626 C．724 D．709
8. 深度为5的二叉树至多有个结点。
A．16 B．31 C．32 D．10
9.具有n(n>0)个结点的完全二叉树的深度为。
A．?log2(n)?B．? log2(n)?C．? log2(n) ?+1 D．?log2(n)+1?
10. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A．1/2 B. 1 C. 2 D. 4
11. 在下图中，从顶点1出发进行深度优先遍历可得到的序列是。
A. 1 2 3 4 5 6 7
B. 1 4 2 6 3 7 5
C. 1 4 2 5 3 6 7
D. 1 2 4 6 5 3 7
12. 请指出在顺序表(2,5,7,10,14,15,18,23,35,41,52)中，用二分法查找关键码12需做次关键码比
较。
A．5 B．4 C．3 D．2
13. 下列排序算法中不稳定的是。
A．快速排序B．归并排序C．冒泡排序D．直接插入排序
14. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放
入已排序序列的正确位置上的方法，称为。
A．希尔排序B．冒泡排序C．插入排序D．选择排序
15. 一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的
一次划分结果为。
A．38,40,46,56,79,84 B．40,38,46,79,56,84
C. 40,38,46,84,56,79 D．40,38,46,56,79,84
二、判断题（共10小题，每题1分，共计10分）
1. 顺序表中逻辑上相邻的元素的物理位置必定相邻。（）
2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列。（）
3. 二叉树是非线性结构，所以它不能用顺序结构存储。（）
4. 一棵度为2的树与一棵二叉树是一样的。（）
5. 线性表是具有n个数字的有限序列（n≠0）。（）
6. 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。（）
7. 快速排序在被排序的数据完全无序的情况下最易发挥其长处。（）
8. 一棵二叉排序树，用先序遍历，可以得到各结点键值的递增序列。（）
9. 数据结构中，与所使用的计算机无关的是数据的存储结构。（）
10. 平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于1。（）
三、填空题（共10空，每空2分，共计20分）
1. 递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是①。
2. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第②次匹配成功。
3. 由3个结点所构成的二叉树有③种形态。
4. 已知一无向图G=(V，E)，其中V={a, b, c, d, e}，E={(a, b), (a, d), (a, c), (d, c), (b, e)}，从顶点a开始遍历
图，采用④______遍历方法能够得到序列a b e c d。
5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是⑤_____________。
6. 判定一个栈ST（最多元素为m0）为空的条件是⑥。
7. 下面给定二叉树的
先序遍历序列为⑦，
中序遍历序列为⑧，
后序遍历序列为⑨。
8. 已知有向图如下所示，其中顶点A到顶点C的最短路径长度是⑩
_________。
四、应用题（共4小题，每题5分，共计20分）
1. 下列程序段的输出结果为（栈的元素类型SElem Type为char）。
void main( )
{ Stack S;
Char x,y;
InitStack(S);
X=’c’;y=’k’;
Push(S,x); Push(S,’a’); Push(S,y);
Pop(S,x); Push(S,’t’); Push(S,x);
Pop(S,x); Push(S,’s’);
while(!StackEmpty(S)){ Pop(S,y);printf(y); };
Printf(x);
}
2. 有一稀疏矩阵用下图所表示的三元组存储，
3. 设哈希函数H(K)=k%13,给定键值序列为
19,1,23,14,55,20,84,27,68,11,10,77，处理冲突的方法为线性探测再散列，试在0~18的散列地址空间中对该关键字序列构造哈希表，并计算该表的成功查找的平均查找长度。
4.用序列（46，68，45，139，70，58，101，10，88，94）建立一个二叉排序树，画出该树，并求在等概
率情况下查找成功的平均查找长度。
五、算法设计题（共2小题，共计20 分）
1. 试写一算法，对单链表实现就地逆置。（8分）
2. 先从键盘输入n个字母生成无序数组，利用冒泡法对数组排序后，再从键盘输入一
个字符进行折半查找。（12分）
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）
数据结构试卷1 一、单项选择题：(每小题2分，共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。 A. first->next == NULL; B. first == NULL; C. first->next == first; D. first != NULL; 3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。 A．y B．(a, b) C．(x,(a, b)) D．x 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择 B.二路归并 C.交换 D.插入 二、填空题（每空1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性
数据结构试卷 一、单项选择题（本大题 共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1 . 下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C. 链队列 D.栈 2 . 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3 . 已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear 指向 队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4 . 递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C. 队列 D. 线性表 5 . 设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）A.求子串 B.串联接 C.串匹配D.求串长 6 . 对于广义表A，若head(A)等于tail(A)，则表A为（） A.() B.(()) C.((),()) D.((),(), ()) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一 定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度 为l的结点个数是3，度为2 的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3 个程序段，第一程序段的执行次数为错误！未找到引用源。，第二个程序段执 行次数为4n，第三个程序段的执行次数 为0.06错误！未找到引用源。，则该算法的时间复 杂度为（）。 A．O（n）B ．O（错误！未找到引用源。） C ．O（错误！未找到引用源。）D．O （错误！未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={
数据结构试卷（一） 一、选择题（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 数据结构试卷 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（） A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3个程序段，第一程序段的执行次数为错误!未找到引用源。，第二个程序段执行次数为4n，第三个程序段的执行次数为0.06错误!未找到引用源。，则该算法的时间复杂度为（）。 A．O（n）B．O（错误!未找到引用源。）C．O（错误!未找到引用源。）D．O （错误!未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ 《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈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 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： 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} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 一、单项选择题（将其号码填在题干后的号码内，每小题2分，共10分） 1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（） A.1，3，2，4 B.2，3，4，1 C.4，3，1，2 D.3，4，2，1 2.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（） A.直接插入排序 B.起泡排序 C.快速排序 D.直接选择排序 3.对n 个记录的文件进行二路归并排序，总的时间代价为 A.O（nlog 2n） B.O（n 2） C.O（log 2n） D.O（n） 4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（） A.9 B.11 C.12 D.不确定 5.下面关于B 树和B +树的叙述中，不正确的是 A.B 树和B +树都是平衡的多分树 B.B 树和B +树都是可用于文件的索引结构 C.B 树和B +树都能有效地支持顺序检索 D.B 树和B +树都能有效地支持随机检索 二、填空题（每空2分，共20分）1.从逻辑结构看，线性表是典型的，树是典型的。 2.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为，按列优顺序存储，元素A[6,6]的存储地址为。 3.若按层次顺序将一棵有n 个结点的完全二叉树的所有结点从1到n 编号，那么当i 为且小于n 时，结点I 的右兄弟是结点，否则结点i 没有右兄弟。 4.求具有最小带权外部路径长度的扩充二叉树的算法称为算法。堆排序中建堆的方法称作。 5.6阶B 树中，每个结点至多包含个关键码，除根和叶结点外，每个结点至少包含个关键码。 三、简答题（每小题6分，共18分） 1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。 2.请简述散列法存储中处理碰撞（冲突）的两类基本方法。 3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？ 四、求解下列问题（每小题6分，共30分） 1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。 2.请画出下面的树所对应的二叉树。 3.从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。 4.请画出下面带权图的一棵最小生成树。 5.对于下面的稀疏矩阵 1）画出其三元组法存储表示。 2）画出其行—列法（十字链表法）存储表示。 五、算法题（6分） 有一个链接方式存储的线性表，表中每个结点包括两个指针，其结点用PASCAL 语言描述如下：TYPE pointer=↑node; node=RECORD info:datatype; link1,link2:pointer END; 其中link1是指向结点的下一个结点的指针，link2是指向结点的前一个结点的指针,如图所示。p 和q 都是pointer 类型的变量，现要将q 所指的新结点插入表中p 所指结点的前面（说明：p 所指的不是链表的第一个结点）。请用PASCAL 语句写出该插入的关键步骤。（部要求写完整的算法，只要求用几个语句写出关键步骤。） 《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 数据结构习题集含答案 目录 选择题 第一章绪论 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．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 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 。 习题一 一、选择题 ( 每小题 2 分，共 20 分 ) 1．下列程序段的时间复杂度为（）。 i=0，s=0； while (s 一、判断题： 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、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。数据结构试卷1(含答案)
数据结构试卷和答案
数据结构试卷带答案
数据结构考试试题
数据结构试题及答案
数据结构试题(含答案)
数据结构试卷
数据结构试卷B卷(含答案)
数据结构考试题库含答案
数据结构试题(含答案)
数据结构试卷一与答案
数据结构试题及答案
数据结构试卷及答案压缩版
相关主题
文本预览