数据结构复习样题答案
一. 单项选择题（共12分）
1. B
2. A
3. A
4. D
5. C
6. D
7. B
8. C
二. 填空题(共12分)
9. 数据对象、数据关系、基本操作
10. 从表中任一结点出发均可找到表中其他结点 11. 字符依次对应相同且长度相同 12. 33
13. 各结点均无左孩子 14. n-1
15. 在排序过程中需要访问外存 16. 散列
三. 解答题（共36分）
17．（5分）后序线索
18.（10分）已知一个长度为12的表为
（Jan ，Feb ，Mar ，Apr ，May ，June ，July ，Aug ，Sep ，Oct ，Nov ，Dec ） （1） 试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大
小）。画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。
（2） 设哈希表长度为13，哈希函数H （k ）= ?i/2?，其中i 为关键字k 中第一个字母在字母
表中的序号（例如A 和D 的序号分别为1和4），用链地址法解决冲突。请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。
Jan
Feb
Mar
Apr
June May
July
Aug
Sep
Oct Nov
Dec
成功的平均查找长度＝42/12
19.（5分）假设电文中仅由a 到h 共8个字母组成，字母在电文中出现的频度依次为
7，19，2，6，32，3，21，10
请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并写出这8个字母相应的哈夫曼编码。
20.（8分）若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给出 （1） 步长为4的一趟希尔排序的结果； （2） 初始大根堆。 答：（1） （12，7，25，29，19，23，26，41） （2） （41，26，23，25，29，12，7，19）
21.（8分）对于右边的带权图G ，请 （1） 画出G 的邻接矩阵；
（2） 画出G 的最小生成树。 答：（1） （
2）
??????
????????∞∞∞∞072377098290638047640
四. 算法题（共30分）
22．（5分）函数f22定义如下，其中函数调用Insert(L, i, k)在顺序表L的第i位置插入k。
void f22(SqList &L, int i) {
if (i > 0) {
f22(L, i-1);
for (int k=1; k<=i; k++)
Insert(L, i, k);
}
}
设有空顺序表L ＝（），请写出调用递归函数f22(L,3)后
（1） L的长度：6
（2）L ＝（1，2，3，2，1，1 ）
23.（5分）算法f23(L)将带头结点的单链表L逆置。请在画线处填空。
void f23(LinkList &L) {
LinkList p = L->next;
L->next = NULL ;
while ( p ) {
LinkList s = p->next ;
p->next = L->next;
L->next = p ;
p = s;
}
}
24.（5分）s是一个升序静态查找表，请简要说明函数调用f24(s, 1, s.length, k)
的意义。
int f24(SSTable s, int low, int high, KeyType k) {
if (low>high) return 0;
int mid=(low+high)/2;
if (k==s.elem[mid].key) return mid;
if (k>s.elem[mid].key) return f24(s,mid+1,high,k);
else return f24(s,low,mid-1,k);
}
答：在s中递归折半查找k。
25．（5分）请对以下函数填空，实现求二叉树T中各结点的子孙总数，并填入结点的DescNum域中的算法。
int f25(BiTree T) {
if ( !T ) return -1;
else {
T->DescNum = f25(T->lchild) +
f25(T->rchild) +
2 ;
return T->DescNum;
}
}
26．（5分）图的邻接矩阵表示和算法f26描述如下：
#define MaxNum 5
typedef struct {
char vexs[MaxNum];
int arcs[MaxNum][MaxNum];
int n,e;
} MGraph;
int f26(MGraph G, int i) {
int d=0;
for (int j=0; j if (G.arcs[i][j]) d++; if (G.arcs[j][i]) d++; } return d; } 已知一个图G的邻接矩阵如右所示， (1)给出执行算法调用f26(G,4)的返回值；答：5； (2)简述该算法返回值的意义。答：求图G第i顶点的度。 27．（10分）请设计实现删除单链表中值相同的多余结点的算法，先简述算法思想，然后写出算法的C语言描述。 void purge(LList L) { // 删除链表中的“冗余”元素 LList s, q, p = L->next; while ( p ) { // p 指向当前被考察的结点 q = p; while (q->next) // 考察 q 所指后继结点 if (q->next->data != p->data) q = q->next; else // 修改指针并释放结点空间 { s = q->next; q->next = s->next; free(s); } p = p->next; }// while p }//purge 数据结构试题及答案 一、单项选择题 (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 数据结构实验报告题目：动态查找表 学院计算机 专业计算机科学与技术年级班别2009级 2 班 学号3109005935 学生姓名黄丽敏 指导教师吴伟民 成绩____________________ 2011年6月 一. 动态查找表： 抽象数据类型动态查找表的定义如下： ADT DynamicSearchTable { 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字 数据关系R：数据元素同属一个集合。 基本操作P： InitDSTable(&DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable(&DT) 初始条件：动态查找表DT存在。 操作结果：销毁动态查找表DT。 SearchDSTable(DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。 InsertDSTable(&DT,e); 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。 DeleteDSTable(&DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 TraverseDSTable(DT,visit()); 初始条件：动态查找表DT存在，visit是对结点操作的应用函数。 操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败。 }ADT DynamicSearchTable 二. 存储结构定义： 公用头文件DS0.h和宏定义: #include 《数据结构》题库及答案 一、选择题 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 的存放位置是 。 操作系统实验报告 学生学院____ 计算机学院______ 专业班级13级计科9 学 号 学生姓名 指导教师 李敏 2015年12月29日 实验一进程调度实验 一、实验目的 用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。 二、实验内容和要求 设计一个有N个进程共行的进程调度程序。要求采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程），时间片轮转算法，多级反馈队列调度算法这三种算法。 每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。 重复以上过程，直到所要进程都完成为止。 三、实验主要仪器设备和材料 实验环境 硬件环境：IBM-PC或兼容机 软件环境：C++、C语言编程环境 四、实验方法 1、编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。 “最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。 静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。 动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。 例如：在进程获得一次CPU后就将其优先数减少1。或者，进程等待的时间超过某一时限时增加其优先数的值，等等。 2、编写并调试一个模拟的进程调度程序，采用“轮转法”调度算法对五个进程进行调度。轮转法可以是简单轮转法、可变时间片轮转法，或多队列轮转法。 简单轮转法的基本思想是：所有就绪进程按FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。如果运行进程用完它的时间片后还为完成，就把它送回到就绪队列的末尾，把处理机重新分配给队首的进程。直至所有的进程运行完毕。 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)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 单选题(每题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 ) 操作系统实验报告 学院_____计算机学院_______ 专业______软件工程________ 班级______ ________ 学号_____ _______ 姓名_______ _________ 指导教师 （2010年10 月） 学号：姓名：协作者：________ 实验__一__题目__ 进程调度___第周星期___ 一、实验目的 用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。 二、实验内容和要求 编写并调试一个模拟的进程调度程序，采用“轮转法”调度算法对五个进程进行调度。 ·每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行的时间、已用CPU时间、进程状态等。 ·进程的优先数以及需要的运行时间事先由人为指定（也可以随机数产生）。 ·如果运行一个时间片后进程的已占用CPU时间已达到所需要的运行时间，则撤销该进程，如果还未达到，则把它送回队尾。 三、实验主要仪器设备和材料 实验环境 硬件环境：IBM-PC 或兼容机 软件环境：C语言编程环境 四、实验原理及设计方案 1、实验原理 将程序顺序的输入进程队列后，开始执行程序，当运行了一个时间片后，如果进程所占的CPU时间达到所需的运行时间时，该进程完成，并撤销该进程，否则则把进程送回队尾。 2、设计方案 用一个进程控制块（PCB）表示进程。输入进程名称，优先级，运行时间后，通过模拟系统对进程采用“轮转法”调度，得到各个时间片进程的运行情况。 3、相关数据结构的说明 struct pcb // 定义进程控制块 PCB { 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 一、单项选择题 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; 数据结构设计性实验报告 课程名称_____ ____ 题目名称 学生学院 专业班级 学号 学生姓名 指导教师 2010 年 7 月 6 日 抽象数据类型：树的实现 一．需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。 二．实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 三．实验环境 1、硬件：PC机 2、软件：Microsoft V isual C++ 6.0 四．设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j ≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有 数据结构Ａ复习要点 第1章基础知识 算法与数据结构（数据结构概念、逻辑结构、数据存储结构示等） 数据抽象和抽象数据类型（数据结构规范、实现） 算法分析的基本方法（时间复杂性、空间复杂性） 第2章线性表 线性表的顺序和链接表示 理解在顺序表、单链表上实现线性表运算，能设计相应算法程序 顺序和链接表示的优缺点比较 第3章堆栈和队列 了解栈和队列的概念、特点 理解顺序栈和循环队列运算的实现 中缀表达式与后缀表达式的转换 后缀表达式计算 第4章数组和字符串 一般数组存储方法 三元组存储稀疏矩阵的方法 三元组表示的快速矩阵转置方法 字符串的概念、KMP算法及其改进 第5章树 二叉树的定义、性质及二叉链表 理解二叉树的遍历算法（遍历结果、算法设计），能设计相应算法程序 堆、堆的建立和调整 森林与二叉树的相互转换 哈夫曼树构造、哈夫曼编码、WPL计算 第6章集合与搜索 理解有序表的顺序搜索算法 理解对半搜索算法 平均搜索长度的计算 第7章搜索树 理解二叉搜索树的定义、性质和插入、删除算法 二叉平衡树的定义及插入算法 B-树的定义和插入、删除方法 第8章散列表 掌握散列函数的相关概念 散列函数 解决冲突的开地址法（线性探查法，二次探查法、双散列法） 第9章图 图的基本概念和存储结构 理解图的算法（结果）：遍历、拓扑排序、最小代价生成树、关键路径、最短路径第10章内排序 三种简单排序算法、快速排序和两路合并排序算法、过程、结果 排序算法的时间复杂度（最好、最差，平均）、稳定性 第11章文件 文件的基本概念 初始游程的生成及竞赛树 考试样题 填空题 写出表达式a*b+c/d的后缀形式________。 已知一无向图G=(V,E)，其中V={a,b,c,d,e}，E={(a,b), (a,d), (a,c) (d,c), (b,e)}，现用某一种遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__________遍历方法。 在顺序表长度为n中，平均在表中插入一个元素需要移动元素的个数可用计算公式为________。 一个表长为n的线性表，其排序时间最快为。 选择题 具有n 个顶点的有向完全图中，边的总数为（）条。 A）n（n+1） B）n（n-1） C）n（n-1）/2 D）n（n+1）/2 设一个栈输入序列是1、2、3、4、5，则下列序列中不可能是栈的输出序列是（）。 A）32541 B）15432 C）14523 D）23145 二叉树的前序遍历为EFHIGJK，中序遍历序列为HFIEJKG。该二叉树根结点的右子树的根是（） A) E B) F C) G D) H 对有14个元素的有序表A[1]-A[14]作对半查找，查找元素A[4]时的被比较元素依次为（） A. A[1],A[2],A[3],A[4] B.A[7],A[3],A[5],A[4] C. A[1],A[2],A[7],A[4] D.A[7],[A5],A[3],A[4] 设有一个长度为100且已排好序的表，用对半搜索进行查找，若搜索不成功，则至少要比较______次。 （） A．9 B．8 C．7 D．6 简答题 用一维数组存放的一棵完全二叉树如图所示： 图 写出前序、中序、后序遍历该二叉树时访问结点的顺序。 图的邻接表表示一个给定的无向图。 （1）给出从顶点v1开始，用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，用广度优先搜索法进行遍历时的顶点序列。 重庆文理学院软件工程学院实验报告册专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 步骤#define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); scanf("%d",&l->elem[i]); i++； px(l,i); l->last++; for(i=0; i<=l->last; i++) { printf("%d ",l->elem[i]); } printf("\n"); } void px(SeqList *A,int j) { int i,temp,k; for(i=0;i 一、单选题（每题 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; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B ) 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网是一种（D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（ A ）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 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、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验内容 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; 数据结构考试考试(带答案) ————————————————————————————————作者：————————————————————————————————日期： ××科技大学成都学院二零零八至二零零九学年第一学期 数据结构课堂测试（60分钟）闭卷考试时间： 题号一二三总分评卷教师 分数 一．填空题（每空2分，共40分）； 1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效 率。 2.下面程序段的时间复杂度为___O(n2)______。(n>1) for(i = 1; i <= n; i++) for(j = 1; j <= i; j++) x = x + 1; 3.静态链表中指针表示的是______下一结点的地址______。 4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___ 位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。 5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。 6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时， 需向后移动__n-i+1__个元素。 7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。 8.带有一个头结点的单链表head为空的条件是_________head->next= =NULL__________。 9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。 10.在hq的链队列中，判定只有一个结点的条件是 __hq.front->next==hq.rear________。 11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。 12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。 13.空串是_______长度为0的串______，其长度等于___0________。 14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数 _________ 。 二．单项选择题（每题2分，共30分）；（说明：请将答案填入下表中）题号 1 2 3 4 5 6 7 8 9 10 答案 A A B B D B C B B C 题号11 12 13 14 15 答案 A A C D D 1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删 除运算，则利用（A）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 2.设a1、a2、a3为3个结点，则如下的链式存储结构称为：A 数据结构习题集含答案 目录 目录 (1) 选择题 (2) 第一章绪论 (2) 第二章线性表 (4) 第三章栈和队列 (6) 第四章串 (7) 第五章数组和广义表 (8) 第六章树和二叉树 (8) 第七章图 (11) 第八章查找 (13) 第九章排序 (14) 简答题 (19) 第一章绪论 (19) 第二章线性表 (24) 第三章栈和队列 (26) 第四章串 (28) 第五章数组和广义表 (29) 第六章树和二叉树 (31) 第七章图 (36) 第八章查找 (38) 第九章排序 (39) 编程题 (41) 第一章绪论 (41) 第二章线性表 (41) 第三章栈和队列 (52) 第四章串 (52) 第五章数组和广义表 (52) 第六章树和二叉树 (52) 第七章图 (52) 第八章查找 (52) 第九章排序 (57) 选择题 第一章绪论 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、研究算法中的输入和输出关系 数据结构实验 实验四、图遍历的演示。 【实验学时】5学时 【实验目的】 （1）掌握图的基本存储方法。 （2）熟练掌握图的两种搜索路径的遍历方法。 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示连通的无向图上，遍历全部结点的操作。 【基本要求】 以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 教科书图7.33。暂时忽略里程，起点为北京。 【实现提示】 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，…，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 【选作内容】 （1）借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 （3）正如习题7。8提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。 【源程序】 #include 数据结构复习题 一、单选题(每小题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}；数据结构试题库答案
数据结构实验报告-动态查找表实验报告
《数据结构》题库及答案
2015广工操作系统实验报告(文档最后含源码下载地址)
数据结构期末考试试题及答案
数据结构试题及答案(10套最新)
广工_操作系统_实验报告
数据结构复习题目和答案
算法与数据结构题库与答案
数据结构-树的实现实验报告
数据结构A复习要点及样题(南邮)
数据结构实验答案(1)
数据结构试题及答案(10套最新)
数据结构实验一 实验报告
数据结构考试考试(带答案)
数据结构考试试题库含答案解析
数据结构实验四五六
大学数据结构期末考试试题(有答案)
相关主题
文本预览