10-11学年第一学期计算机科学与技术专业张先伟、肖爱梅
一、填空（每空1分，共20分）
1、深度为k的完全二叉树至少有10个叶结点的二叉树中有2的结点。
2、设数组a[1..5,1..8]的基地址为200，每个元素占2个存储单元，若以行序为主序顺序存储，则元素
a[4,6]的存储地址为
3
4
5、要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个
结点的地址为t, 。
6、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的
i列中所有非零元素个数之和等于顶点i
7、对于表长为n的顺序存储的线性表，访问结点的时间复杂度为删除结点的时间复杂度为。
8、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点
编号为1
9、己知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找100时，
需
10、Dijkstra
11、如果T2是由树T1转换而来的二叉树，那么T1中结点的后序遍历就是T2
12、广义表A= (d)则Head(Tail(Head(Tail(Tail(A)))))的值为
13、设无向连通图的顶点个数为n，则该图最少有
二、选择（每题2分，共20分）
1、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是
A．快速排序B．堆排序C．归并排序D．直接插入排序
2、有五个元素按5，4，3，2，1
A． 3 2 1 5 4 B． 4 5 3 1 2 C． 3 4 5 2 1 D． 2 3 4 1 5
3、无向图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)}，对该图进行深度优先
遍历，得到的顶点序列正确的是
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
4、链表不具有的特点是
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性表长度成正比
5、在一棵三叉树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度
为0的结点数为
A．4 B．8 C．6 D．5
6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除
一个元素，再加入两个元素后，rear和front的值分别是
A．2和4 B．1和 5 C．4和2 D．5和1
7、若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的
结果，则该排序算法只能是
A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序
8、对稀疏矩阵进行压缩存储目的是
A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度
9、在下面的程序段中，对x的赋值语句的频度为
for ( i=1; i<= n; i++)
for ( j=1; j<= n; j++)
x=x+1;
A．O(2n) B．O(n) C．O(log2n) D．O(n2)
10、双向链表中，在指针p指向的结点前插入指针q
A．p->prior=q; q->next=p; p->prior->next=q; q->prior=q；
B．p->prior=q; p->prior->next=q; q->next=p; q->prior=p->prior;
C．q->next=p; q->prior=p->prior; p->prior->next=q; p->prior=q;
D．q->prior=p->prior; q->next=q; p->prior=q; p->prior=q;
三、应用题（40分）
1、（6分）已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。
请回答下列问题：
(1)请画出对应的图G。
(2)画出图G的邻接表存储结构。
2、（6分）对于关键字序列(503，87，512，61，908，120，897，275，653，462), 建立初始堆（小顶
堆）。
3、（8分）已知一棵二叉树的先序序列：A B D H I M E J C F K L G，中序序列：H D I M B J E A K F L C G，请
画出该二叉树，并简单说明理由。
4、（6分）采用哈希函数H(k)=3*k MOD 13，并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中
对关键字序列22、41、53、46、30、13、1、67、51，构造哈希表（画示意图）。
5、（6分）下图为无向带权图，用克鲁斯卡尔算法构造其最小生成树，并写出选边的顺序。
6、（8分）对关键字序列{30,15,28,20,24,10,12,68,35}，
（1）构造一棵二叉排序树；
（2）对初始序列构造一棵二叉平衡树。
四、算法阅读与设计题(本大题共2小题，共20分)
1、（8分）已知下列程序，Ls指向带头结点的单链表。
Typedefstruct node {
DataType data;
struct node * next;
} * LinkList;
void f30( LinkList Ls )
{ LinkList p, q;
q = Ls->next;
if ( q && q->next ) {
Ls->next = q->next;
p=q
while ( p->next )
p = p->next;
p->next = q;
q->next = NULL;
}
}
请回答下列问题：
(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。
(2)请简述算法的功能。
2、（12分）写出二叉树的二叉链表类型，设计算法求二叉树中度为1的结点的数目。（用自然语言给出设计思想，再用代码实现。
06-07学年第二学期计算机科学与技术专业张先伟
一．填空（每空1分，共20分）
1.数据的存储结构主要有两类:________存储结构和________存储结构。
2.栈与队列都是限定性的数据结构，栈的操作特性是____________，队列的操作特性是____________。
3.在顺序表中插入或删除一个元素，需要平均移动________元素，具体移动的元素的个数与______________有关。
4.组成串的数据元素只能是________，空串的长度是________。
5.广义表（a，（b））的深度是________，表尾是________。
6.深度为K的完全二叉树至少有____________个结点，具有100个结点的完全二叉树的深度是________。
7.N个定点的无向连通图至少有___________条边，图的遍历有广度优先搜索遍历和________搜索遍历两种方法。
8.在一个单链表中在指针P所指结点之后插入一个S结点，应执行的操作依次是：S —>next=______________和P—>next=________________。
9.影响哈希表查找长度的主要因素是____________________、____________________和哈希因子。
10.折半查找必须基于____________存储的________________表进行。
二．选择（每题2分，共20分）
1．一个带头结点的单链表，头指针为head，判断其是否为空的条件是________。
A、head == NULL
B、head—>next == NULL
C、head != NULL;
D、head—>next == head 2．设栈的输入序列是1，2，3，4，则________不可能是其输入序列。
A、1，2，4，3
B、2，1，3，4
C、4，3，1，2
D、3，2，1，4
3．稀疏矩阵的压缩存储不包含下面哪种方式________。
A、三元组顺序表
B、行逻辑连接的顺序表
C、邻接多重表
D、十字链表
4．有N个叶结点的哈夫曼树的结点总数是________。
A、不确定
B、2N
C、2N+1
D、2N-1
5．下列排序方法中，待排记录有序时花费时间反而最多的是________。
A、快速排序
B、希尔排序
C、起泡排序
D、堆排序
6．下面有关二叉树的说法正确的是________。
A、二叉树的度为2
B、二叉树的度可以小于2
C、二叉树中至少有一个节点的度数为2
D、二叉树中任何一个结点的度数都为2
7．堆的形状是一棵________。
A、二叉排序树
B、满二叉树
C、完全二叉树
D、平衡二叉树
8、关键路径是AOE网中________。
A、从源点到汇点的最长路径
B、从源点到汇点的最长回路
C、从源点到汇点的最短路径
D、从源点到汇点的最短回路
9、循环队列是空队列的条件是________。
A、Q—>rear == Q—>front
B、（Q—>rear+1）%maxsize == Q—>front
C、Q—>rear == 0
D、Q—>front == 0
10、在有向图G的拓扑排序序列中，若定点Vi在顶点Vj之前，则下列情形不可能出现的是________。
A、G中有弧
B、G中有一条从Vi到Vj的路径
C、G中没有弧
D、G中有一条从Vj到Vi的路径
三、问答与综合（共5个题目，36分）
1、（6分）什么是数据的逻辑结构？简述常见的逻辑结构的分类及其特点。
2、（8分）已知二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，
（1）构造该二叉树，并简单说明理由；
（2）将该二叉树转换成相应的树（或森林）。
3、（8分）对于如下的无向网
（1）写出其邻接表；
（2）按照Prime算法求网的一棵最小生成树（写出过程）。
4、（8分）对下面的二叉排序树：
（1）求二叉排序树在等概率查找时平均查找长度；
（2）画出插入关键码16后的结果；
（3）画出对原树删除关键码40后的结果。
5、（6分）初始关键字序列为（30，4，28，58，5，13，90，47，18）
（1）写出对其做一趟直接插入排序后的结果；
（2）对其初始序列以30为枢轴做一次快速排序后的结果。
四、算法阅读（共两个题目，12分）
1、阅读下面算法，说明该算法的功能，并分析其时间复杂度（已知h是带头结点的单链表的头指针）
Void rever( lnode *h)
{ lnode p,q;
p = h->next;
h->next = null;
while( p)
{ q = p;
p = p->next;
q->next = h->next;
h->next = q;
} //end while
} //end rever
2、下面是折半查找算法，在____处将算法语句补充完整。
int Search ( SSTable ST, KeyType key)
{ low = 1; high = ST.lengh;
while( __________)
{ mid = ________________;
if ( EQ( key, ST.elem[mid].key ) )
return mid;
else if ( LT( key, ST.elem[mid].key ) )
________________;
else
low = mid + 1;
}
return 0;
}
五、编写算法（共1题，12分）
编写算法，遍历二叉树，求该二叉树叶子节点的个数。
int LeafNum ( lnode *root )
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. 计算机算法指的是（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）
2014 上数据结构期末复习大纲 一. 期中前以期中考试试卷复习，算法要真正理解 二、二叉树、图、排序算法将是考试重点（占60%左右） 三、要掌握的算法 1. 二叉树的链表表示 2.建立二叉树的链表存储结构 3. 先序、中序、后序遍历二叉树（递归算法） 4. 遍历算法的应用（如求二叉树的结点数） 5.建立huffman树和huffman编码 6. 图的邻接矩阵表示和邻接链表表示 7.图的深度优先遍历和广度优先遍历算法 8. 有向图求最短路径（迪杰斯特拉算法） 9. 直接插入排序算法 10. shell 排序(排序过程) 12. 堆排序（排序过程）
练习题 1. 有8个结点的无向图最多有 B 条边。 A ．14 B. 28 C. 56 D. 112 2. 有8个结点的无向连通图最少有 C 条边。 A ．5 B. 6 C. 7 D. 8 3. 有8个结点的有向完全图最多有 C 条边。 A ．14 B. 28 C. 56 D. 112 4. 用邻接表表示图进行广度优先遍历时，通常是采用 B 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 5. 用邻接表表示图进行深度优先遍历时，通常是采用 A 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 6. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是*（ C ） A ．0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110
数据结构期末考试题及标准答案
————————————————————————————————作者：————————————————————————————————日期：
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.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。
3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？
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.以顺序方式存储，且数据元素有序
第1章概论 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①Ｃ、数据信息在计算机中的②A以及一组相关的运算等的课程。 ①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 计算机算法指的是① C ，它必具备输入、输出和② B 等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 3.下面程序段的时间复杂度是D for(i=0;i
2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.
数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.
数据结构与算法分析-六套期末复习题(含答案)
试题一 一、单项选择题（每小题2分，共20分） （1）以下数据结构中哪一个是线性结构？（） A）有向图B）队列C）线索二叉树D）B树 （2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。 A）p=q; p->next=q; B）p->next=q; q->next=p; C）p->next=q->next; p=q; D）q->next=p->next; p->next=q; （3）（）不是队列的基本运算。 A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空D）读取队头元素的值 （4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。 A）14 B）5 C）6 D）8 （5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。 A）11 B）35 C）19 D）53 以下6-8题基于下图： （6）该二叉树结点的前序遍历的序列为（）。 A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树结点的中序遍历的序列为（）。 A）A、B、C、D、E、G、F B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）B、D、C、A、F、G、E
（8）该二叉树的按层遍历的序列为（）。 A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面关于图的存储的叙述中正确的是（）。 A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 （10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（） A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z 二、（本题8分） 对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 三、（本题8分） 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列：K FBHJ G A 四、（每小题2分，共8分） 设有序列：w={23,24,27,80,28}，试给出： （1）二叉排序树； （2）哈夫曼树； （3）平衡二叉树；
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j
一．是非题 （正确的打“√”，错误的打“×”。） 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’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’
贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j
数据结构复习题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序； 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}；
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.以下与数据的存储结构无关的术语是（c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示
2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。
A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 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 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20}
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序：