haerb大学数据结构期末复习题
《数据结构》复习题
（含部分参考答案版）
一、单杜鳌项选择题
1. 按照数据逻辑结构的不同，可以将数据结构分成 C 。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
2. 下列关于数据结构的叙述中正确的是 A 。
A. 数组是同类型值的集合
B. 递归算法的程序结构比迭代算法的程序结构更为复杂
C. 树是一种线性的数据结构
D. 用一维数组存储二叉树，总是以先序顺序遍历各结点
3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为B
A.逻辑结构
B.顺序存储结构
C.链式存储结构
D.以上都不对
4. 以下关于算法特性的描述中， B 是正确的。
（1）算法至少有一个输入和一个输出
（2）算法至少有一个输出但是可以没有输入
（3）算法可以永远运行下去
A. （1）
B. （2）
C. （3）
D. （2）和（3）
5. 对顺序存储的线性表（a1,a2,…,a n）进行插入操作的时间复杂度是 C 。
A.O(n)
B. O(n-i)
C. (n/2)
D. O(n-1)
6. 链表不具有的特点是A 。
A.可随机访问任一元素
B.插入和删除时不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表的长度成正比
7.线性链表中各链结点之间的地址 C 。
A.必须连续
B.部分地址必须连续
C.不一定连续
D.连续与否无关
8. 以下关于链式存储结构的叙述中， C 是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除操作方便，不必移动结点
9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为D 。
A. dcba
B. acdb
C. abcd
D. cbda
10. 将新元素插入到链式队列中时，新元素只能插入到 B 。
A. 链头
B. 链尾
C. 链中
D. 第i个位置，i大于等于1，大于等于表长加1
11. 设栈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
12.下面 D 是‘abcd321ABCD’的子串。
A. abcd
B. 321ab
C. ‘abc ABC’
D. ‘21AB’
13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存
储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时C 元素相同。
A. a[7，3]
B. a[8，3]
C. a[1，4]
D. ABC都不对
14. 数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000
的内存单元中，则元素A[5，5]的地址为 A 。
A. 1175
B. 1180
C. 1205
D.1210
15.下列广义表中，长度为3的广义表为 B 。
A.（a,b,c,( )）
B. ((g),(a,b,c,d,f),( ))
C. (a,(b,(d)))
D. ((( )))
16. 以下关于广义表的叙述中，正确的是 A 。
A. 广义表是0个或多个单元素或子表组成的有限序列
B. 广义表至少有一个元素是子表
C. 广义表不可以是自身的子表
D. 广义表不能为空表
17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有 D 个
叶结点。
A. 1+2b+3c
B. a+2b+3c
C.2b+3c
D. 1+b+2c
18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是 B 。
A. 100
B. 101
C. 102
D. 103
19. 在有n 个叶子结点的霍夫曼树中，其结点总数为：。
A. n
B. 2n
C. 2n +1
D. 2n - 1
20.具有12个结点的完全二叉树有 B 。
A. 5个叶子结点
B. 5个度为2的结点
C. 7个分支结点
D. 2个度为1的结点
21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x
在y之后，则x和y的关系是 C 。
A. x是y的左兄弟
B. x是y的右兄弟
C. x是y的祖先
D. x是y的后代
22. 先序遍历序列与中序遍历序列相同的二叉树为。
A. 根结点无左子树的二叉树
B.根结点无右子树的二叉树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
23.若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf，则其后序遍历序列为 A 。
A. ceadfb
B. feacdb
C. eacdfb
D. 以上都不对
24.设无向图的顶点个数为n，则该图最多有 C 条边。
A. n-1
B. n(n-1)
C. n(n-1)/2
D. n
25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是
C 。
A. e/2
B. e
C. n+2e
D. n+e
26. 无向图G=（V，E），其中V=｛a,b,c,d,e,f｝,E=｛(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)｝。
对该图进行深度优先遍历，下面不能得到的序列是 D 。
A. acfdeb
B. aebdfc
C. aedfcb
D. abecdf
27.在下述排序方法中，不属于内排序方法的是 C 。
A. 插入排序法
B. 选择排序法
C. 拓扑排序法
D. 归并排序法
28. 直接插入排序在最好情况下的时间复杂度为 B 。
A. O(log2n)
B. O(n)
C. O(nlog2n)
D. O(n2)
29.对有n个记录的表作快速排序，在最坏情况，算法的时间复杂度是 D 。
A. O(n3)
B. O(n)
C. O(nlog2n)
D. O(n2)
30.下面的排序算法中，稳定是 A 。
A. 直接插入排序法
B. 快速排序法
C. 直接选择排序法
D. 堆排序法
二、填空题
1. 一个算法具有5个特性：、、、有零个或多个输入，
一个或多个输出。
2. .设数组a[1…50，1…80]的基地址为2000，每个元素占2个存储单元，若以行序为主序
顺序存储，则元素a[45，68]的存储地址为9174 ；若以列序为主序顺序存储，则元素a[45，68]的存储地址为8788 。
3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取
线性表中的元素时，应采用存储结构。
4.两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。
5. 字符串“abcd”中共有个长度大于0的字串。
6. 广义表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的长度及深度分别
为和。
7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点。
8.若无向图满足有n-1条边的连通图，则该图是树。
9.若无向图中有n个顶点，则其边数最少为n-1 ，最多为n(n-1)/2 。
10.堆排序的时间复杂度和空间复杂度分别为O(nlog2n) 和O(1) 。
三、名词解释
（1）抽象数据类型（2）算法及其特性（3）串的模式匹配（4）优先级队列
（5）完全二叉树（6）堆（7）Huffman编码（8）Huffman树
（9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法
（12）普里姆算法（13）希尔排序（14）快速排序
（15）教材等等相关名次解释题
四、简答题
1. 请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题）
2. 单链表为什么要引入头结点？
3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？
参考答案：
●单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不
能随机访问数据。和其它两种相比，它还节省了空间。
●循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结
点。缺点同单链表的缺点。
●双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前
驱。缺点是增加了空间开销。
4.内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用，怎样分配这部分
存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。
5. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。
问：（1）能否得到下列的输出序列：① B，C，D，E，A；② E，A，B，C，D；
③E，D，C，B，A。
（2）写出所有可能正确的输出序列（至少5种）。
6.用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和
为满的边界条件。
●参考答案：
队空条件为max_size==1;
队满的条件为（max_size+1）%MAXSIZE.
7. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求：
（1）画出该二叉树；
（2）写出该二叉树的先序遍历序列；
（3）画出该二叉树对应的森林。
8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍
历。现已知一棵二叉树的层次序列为AEBGFDIMH，中序遍历序列为GEFAMDBHI。
请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子—兄弟表示，请画出该森林。（西电2004年考研试题）
9. 已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为23、
5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。
10.给定下列图G用两种不同表示法画出该图的存储结构图。
11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。
12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、
锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。
13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。
（1）100，90，80，60，85，75，20，25，10，70，65，50
（2）100，70，50，20，90，75，60，25，10，85，65，80
14.已知一序列（12，70，33，65，24，56，48，92，86，33），问该序列是否是堆？如果
不是，则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电2005年考研试题）
15.试为下列情况选择合适的排序算法：（西电2006年考研试题）
（1）n=30，且要求最坏情况下速度最快；
（2）n=30，且要求既要快，又要排序稳定；
（3）n=2000，要求平均情况下速度最快；
（4）n=2000，要求最坏情况下速度最快，又要节省存储空间。
五、算法设计题
1. 实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。
（教材P74页）
2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value 的新结点并将其插入到当前结点之后。（教材P91页）
（b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前指针指到链表中下一个结点位置。（教材P91页）
3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材P107页）
（b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材P117页）
4.对二叉链表，实现一个函数Parent(*BinTreeNode
*BinTreeNode
其地址，否则返回NULL。（教材P171页）
5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法：
（1）统计二叉树中叶子结点的个数；
（2）交换每个结点的左子女和右子女。
6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的
算法
7.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请
完成下面的入队列和出队列的算法：（西电2004年考研试题）
#define MAXQSIZE 100 //最大队列长度
Type struct｛
Qelemtype *base; //base为队列所在区域的首地址
int length; //队列长度
int rear; //队尾元素位置
｝SqQueue;
Status EnQueue(SqQueue &Q, Qelemtype e)
｛
if ( ①) return ERROR; // 队列满，无法插入
Q.rear= ②; //计算元素e的插入位置
③= e; //在队尾加入新的元素
Q.length++; //队列长度加1
return OK;
｝
Status DeQueue(SqQueue &Q, Qelemtype &e) //删除对头元素，并用e带回其值
｛
if ( ④)return ERROR; //队列满
e=Q.base[ ⑤]; //取队头元素
Q．length --; //队列长度减1
return OK;
｝
8.请运用快速排序思想，设计递归算法实现求n（n＞1）个不同元素集合中的第i（1≤i ≤n）小元素。（西电2004年考研试题）
9.阅读下列函数说明及相应代码，在空白处填入相应语句。
(西电2005年考研试题)
[函数1]
函数palinddrome(char s[])的功能是：判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEVAL”不是。
Int palindrome (char s[])
{char *pi, *pj;
Pi = s; pj =s + strlen(s) – 1; //*strlen(s)函数用于求得串s的串长
While（pi＜pj && ①）{
Pi ++; pi - - ;
}
if ( ②)return - 1;
else return 0;
}
[函数2]
函数insert_sort(int a[],int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。
V oid insert_sort(int a[], int count)
{ int i, j, t;
for (i=1;i＜count;i++){//控制a[i]，…a[count-1]的比较和插入
t = a[i];
j= ③;
while (j≥0&&t＜a[j]){ //在有序部分寻找元素a[i]的插入位置
④;
j - -;
}
⑤;
}
}
10. 假设以数组seq[0…m-1]存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。(西电2006年考研试题) 请给出：
（1）给出循环队列的队满条件和队空条件；
（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；
（3）如果用数组sequ[m…n]来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？
山东大学数据库实验答案2—8
山东大学数据库实验答案2—8 CREATE TABLE test2_01 AS SELECT SID, NAME FROM pub.STUDENT WHERE sid NOT IN ( SELECT sid FROM pub.STUDENT_COURSE ) CREATE TABLE test2_02 AS SELECT SID, NAME FROM PUB.STUDENT WHERE SID IN ( SELECT DISTINCT SID FROM PUB.STUDENT_COURSE WHERE CID IN ( SELECT CID FROM PUB.STUDENT_COURSE WHERE SID='200900130417' ) ) CREATE TABLE test2_03 AS
select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where FCID='300002') ) CREATE TABLE test2_04 AS select SID,NAME from PUB.STUDENT where SID in ( select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='操作系统') intersect select distinct SID from PUB.STUDENT_COURSE where CID in (select CID from PUB.COURSE where NAME='数据结构') ) create table test2_05 as with valid_stu(sid,name) as ( select SID,NAME from PUB.STUDENT where AGE=20 and SID in (select SID from PUB.STUDENT_COURSE) ) select sid,name as name,ROUND(avg(score)) as avg_score,sum(score) as sum_score from PUB.STUDENT_COURSE natural join valid_stu where SID in (select SID from valid_stu) group by SID,NAME create table test2_06 as
大学数据结构期末知识点重点总结(考试专用)
.. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K ）以及这些数据之间的 一组二元关系（关系集合R ）来表示：(K, R) 结点集K 是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系，其中每个关系r （r ∈R ）都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char ）、指针类型（pointer ） b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a ．大Ο分析法：上限，表明最坏情况 b ．Ω分析法：下限，表明最好情况 c ．Θ分析法：当上限和下限相同时，表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （设每个元素需占用L 个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e .插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n ）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n ）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head 和tail 指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n ）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n ）】 e.不足：next 仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch ： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项> <项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式，PostfixExp 为后缀表达式 初始化操作数栈OP ，运算符栈OPND ；OPND.push('#'); 读取InfixExp 表达式的一项 操作数：直接输出到PostfixExp 中； 操作符： 当‘（’：入OPND; 当‘）’：OPND 此时若空，则出错；OPND 若非空，栈中元 素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若 为‘（’，弹出即可 当‘四则运算符’：循环（当栈非空且栈顶不是‘（’&& 当前运算符优先级>栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp 中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP ； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear ；队满：(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树 外部路径长度E ：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和 内部路径长度I ：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i 层（根为第0层，i ≥0）最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点（n>0）的完全二叉树的高度为?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点编号是 (i-1)/2 2) 当2i+1 1.二分搜索一个14个数的数组，查找A[4]所经过的元素有____. 2.一个序列先入栈，再出栈，出栈元素加入队列，生成一个新的顺序（已给出），则栈结构最少需要能保存几个元素_______. 3.一个5000个元素的数据需要排序，在堆排序，基数排序，快速排序里，要求速度最快，选哪一个______. 4.n个结点的m序B树，有____个外部节点。一个5序B树有53个结点，该B树至少有___ 层。 5.已给出一个K=11的散列表已有三个元素，再插入两个元素，则这两个元素的位置是________. 6.已给出一个无序数组，选第一个元素作为基点，快排一趟之后的顺序为____________________. 7.一个图已给3条边，再添加一条边，使其有唯一的拓扑序列，添加的边是_______,拓扑序列为____________. 8已给出一个序列，初始化为最小堆____________________。 1.跳表和散列，分别搜索最小元素写出思想和时间复杂度。 2.已给出一个序列，写出建立A VL树的过程，及删除某一个元素后的结果。 3.已给出一个有向图，写出对应的邻接表，根据Dijkstra算法写出某个顶点到其余各顶点的最短路径。 4.已给出一颗公式化描述的二叉树，画出二叉树并写出前中后序列及转化成森林。 5.无向图用公式化描述，为简化，用数组M表示上三角矩阵。写出A[i,j]到M的映射关系，说明如何求任意顶点i的度。 6.6个有序的序列，20 30 40 60 70 100 通过5次两两合并，生成一个有序的序列，求最少次数的合并过程。 1.删除链表形式的二叉搜索树的最大元素，写出思想，算法实现，时间复杂度。 2.邻接链表表示的图写出算法判断是否存在V->U的路径，以及思想。 东北大学继续教育学院 数据结构II 试卷（作业考核线上1） A 卷 学习中心：奥鹏远程教育沈阳学习中心（直属）[32]院校学号：C09024011930344 姓名何家强 （共 6 页） [ A]1．抽象数据类型的三个组成部分分别为 A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 [ B]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为 A. 数据元素具有同一的特点 B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 [ D]3．下列各式中，按增长率由小至大的顺序正确排列的是 A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100 C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n [B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 [ C]5．设指针p指向双链表的某一结点，则双链表结构的对称性是 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior; [D ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指 针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 A. s->next=q；p->next=s->next； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. q->next=s->next；s->next=p； [A ]7. 栈和队列的共同特点是 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 [D ]8. 对于链队列，在进行插入运算时. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 [B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为 A．4 B．5 C. 6 D. 7 [D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C [ C]11．表达式a*(b+c)-d的后缀表达式是 A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd [B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 [ B]13．下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错 [ B]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的 说法正确的是 A．树的后序遍历与其对应的二叉树的先序遍历相同 B．树的后序遍历与其对应的二叉树的中序遍历相同 C．树的先序序遍历与其对应的二叉树的中序遍历相同 D．以上都不对 [D ]15．下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A．(1)(2)(3) B．(1)(2) C．(1)(3) D．都不对 [D ]16. 二叉树的第k层的结点数最多为 A．2k-1 B.2K+1 数据库实验（一） 熟悉环境、建立/删除表、插入数据 Drop table 表名 update dbtest set test=1 select * from dbscore 1．教师信息(教师编号、姓名、性别、年龄、院系名称) test1_teacher：tid char 6 not null、name varchar 10 not null、sex char 2、age int、dname varchar 10。 根据教师名称建立一个索引。 1、create table test1_teacher( tid char(6) primary key, name varchar(10) not null, sex char(2), age int, dname varchar(10) ) 2．学生信息（学生编号、姓名、性别、年龄、出生日期、院系名称、班级）test1_student：sid char 12 not null、name varchar 10 not null、sex char 2、age int、birthday date（oracle的date类型是包含时间信息的，时间信息全部为零）、dname varchar 10、class varchar(10)。 根据姓名建立一个索引。 2、create table test1_student( sid char(12) primary key, name varchar(10) not null, sex char(2), age int, birthday date, dname varchar(10), class varchar(10) ) 3．课程信息（课程编号、课程名称、先行课编号、学分） test1_course：cid char 6 not null、name varchar 10 not null、fcid char 6、credit numeric 2，1（其中2代表总长度，1代表小数点后面长度）。 根据课程名建立一个索引。 3、create table test1_course( cid char(6) primary key, name varchar(10) not null, fcid char(6), credit numeric(2,1) ) 4．学生选课信息（学号、课程号、成绩、教师编号） test1_student_course：sid char 12 not null、cid char 6 not null、 score numeric 5，1（其中5代表总长度，1代表小数点后面长度）、tid char 6。 4、 create table test1_student_course( sid char(12) , cid char(6) , score numeric(5,1), tid char(6), primary key(sid,cid), 一、选择(2’×15=30’) 1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时 间复杂度为( ) A.O(0) B.O(1) C.O(n) D.O(n2) 2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾 结点，则在进行删除操作时( ) A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都不修改 D.队头、队尾指针都可能要修改 3.设栈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 4.对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( ) A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D) 7.下面关于二分查找的叙述正确的是( ) A.表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序，且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列 D.表必须有序，且表只能以顺序方式存储 8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是( ) A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序 9.下列关于无向连通图特性的叙述中，正确的是( ) I.所有顶点的度之和为偶数 II.边数大于顶点个数减1 《数据结构》模拟卷 一、选择题 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（A ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是：（B ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3. 从逻辑上可以把数据结构分为（C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ D ），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5. 以下数据结构中，哪一个是线性结构（D ）。 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 6. 以下属于逻辑结构的是（C ）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（ C ）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（ C ）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（ C ）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（ B ）的查找速度。 A. 较慢 B. 较快 C. 相同 D.不同 二、填空题 1.二维数组是一种非线性结构，其中的每一个数组元素最多有___2___个直接前驱（或直 接后继）。 2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_「(K+1)／3」_行的元素。 3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_指针__域的值。 4.在一个链式栈中，若栈顶指针等于NULL则为__空栈__。 5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用， 它们都需要利用栈保存调用后的__返回___地址。 6.在一棵树中，_叶子_结点没有后继结点。 7.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为__3__。假定 根结点的层数为0。 8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差 的绝对值不超过__1____。 9.n (n﹥0) 个顶点的无向图最多有_n（n-1）/2__条边，最少有___0___条边。 10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为_ 稠密_索引，若对应数据对象表中的若干个表项，则称此索引为__稀疏__索引。 三、判断题 1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的(对) 2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间 的逻辑顺序(错) 3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针(对) 实验报告 实验课程：数据结构 实验项目：实验三互联网域名查询 专业：计算机科学与技术 班级： 姓名： 学号： 指导教师： 目录一、问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析 二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码 一、问题定义及需求分析 （1）实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以看成是树的遍历问题。 （2）实验任务 设计搜索互联网域名的程序。 （3）需求分析： 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。 4)通过层次优先遍历搜索。 二、概要设计： 采用孩子兄弟链表存储结构完成二叉树的创建； 主程序流程： 创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序 模块关系： 输入域名 创建孩子兄弟树 层次优先遍历输出结果 深度优先遍历输出结果 结束 三、详细设计 孩子兄弟链表结构： typedef struct CSNode{ ElemType data[10]; struct CSNode *firstchild, *nextsibling; }*CSTree; 山东大学操作系统实验报告4进程同步实验 计算机科学与技术学院实验报告 实验题目：实验四、进程同步实验学号： 日期：20120409 班级：计基地12 姓名： 实验目的： 加深对并发协作进程同步与互斥概念的理解，观察和体验并发进程同步与互斥 操作的效果，分析与研究经典进程同步与互斥问题的实际解决方案。了解 Linux 系统中 IPC 进程同步工具的用法，练习并发协作进程的同步与互斥操作的编程与调试技术。 实验内容： 抽烟者问题。假设一个系统中有三个抽烟者进程，每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草，一个有纸，另一个有胶水。系统中还有两个供应者进程，它们无限地供应所有三种材料，但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者，让它继续提供另外的两种材料。这一过程重复进行。请用以上介绍的 IPC 同步机制编程，实现该问题要求的功能。 硬件环境： 处理器：Intel? Core?i3-2350M CPU @ 2.30GHz ×4 图形：Intel? Sandybridge Mobile x86/MMX/SSE2 内存：4G 操作系统：32位 磁盘：20.1 GB 软件环境： ubuntu13.04 实验步骤： （1）新建定义了producer和consumer共用的IPC函数原型和变量的ipc.h文件。 （2）新建ipc.c文件，编写producer和consumer 共用的IPC的具体相应函数。 （3）新建Producer文件，首先定义producer 的一些行为，利用系统调用，建立共享内存区域，设定其长度并获取共享内存的首地址。然后设定生产者互斥与同步的信号灯，并为他们设置相应的初值。当有生产者进程在运行而其他生产者请求时，相应的信号灯就会阻止他，当共享内存区域已满时，信号等也会提示生产者不能再往共享内存中放入内容。 （4）新建Consumer文件，定义consumer的一些行为，利用系统调用来创建共享内存区域，并设定他的长度并获取共享内存的首地址。然后设定消费者互斥与同步的信号灯，并为他们设置相应的初值。当有消费进程在运行而其他消费者请求时，相应的信号灯就会阻止它，当共享内存区域已空时，信号等也会提示生产者不能再从共享内存中取出相应的内容。 运行的消费者应该与相应的生产者对应起来，只有这样运行结果才会正确。 实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离 输出形式 最小生成树，即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private: int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm(); void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l山东大学软件学院2014-2015数据结构真题
40875][东北大学]20年7月考试《数据结构Ⅱ》考核作业(答案)
山东大学《数据库系统》上机实验答案 详细整理 2013最新版
大连理工大学软件学院2014数据结构期末考试)
山东大学网络教育《数据结构》( A 卷)
数据结构实验-互联网域名查询实验报告
山东大学操作系统实验报告4进程同步实验
东北大学数据结构上机实验报告3
- 淮阴工学院《数据结构》期末样卷
- 大学数据结构期末考试试题(有答案)
- 北京理工大学数据结构试题及答案
- 大连理工大学软件学院2014数据结构期末考试)
- 最新大学数据结构期末考试试题(有答案)
- 大学数据结构 期末考试 模拟题
- 淮海工学院数据结构期末试卷及答案(1)
- 大学数据结构期末考试试题(有答案)
- 北京邮电大学数据结构期末考试试题
- 北方工业大学数据结构期末复习题
- 《数据结构》期终考试试卷(A)-清华大学
- 大学数据结构期末考试试题(有答案)
- 2016年秋国家开放大学《数据结构(本)》期末练习1100分答案16年秋
- 大学数据结构期末知识点重点总结(考试专用)
- 湖南大学数据结构期末考试试题
- 大学数据结构期末考试试题(有答案)
- 杭州电子科技大学数据结构期末复习卷
- 数据结构期终考试试卷A清华大学
- (完整word版)湖南大学数据结构期末考试试题
- 安徽大学2014数据结构期末考试试卷(A卷)