下载文档原格式
华南农业大学期末考试试卷（B卷）2007年1月考试科目：数据结构考试类型：（闭卷）考试时间：120 分钟班级学号姓名考试须知：1．答案必须写在“答题卡”上，写在试卷上不得分。
2．考试结束时，只回收答题卡，不回收试卷。
3. 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩一、选择题（每小题2分，共20分）1、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)2、设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。
A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 43、串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数4、有n个顶点的无向图最多有( )条边。
A．n B．n(n—1) C n(n-1) /2 D. n25、就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡排序B. 希尔排序C. 堆排序D. 快速排序6、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A. 808B. 818C. 1010D. 10207、若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front 和rear，则当前队列的长度是（）。
A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. (rear-front)%m8、以下哪个数据结构，是非线性数据结构（）。
A. 树B. 字符串C. 队列D. 栈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则采用的排序是( )。
适用专业：一、单项选择题（每题2分，共40分）1．算法的时间复杂度是指( )A．执行算法程序所需要的时间B．算法程序的长度C．算法执行过程中所需要的基本运算次数D．算法程序中的指令条数2．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。
A．p = q->next ; p->next = q->next; B．p = q->next ; q->next = p;C．q->next = q->next->next; q->next = q; D．p = q->next ; q->next = p->next; 3．下列叙述中正确的是( )A．线性表是线性结构 B. 栈与队列是非线性结构C．线性链表是非线性结构 D. 二叉树是线性结构4．若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，25．图的广度优先搜索类似于树的（）次序遍历。
A．先根B．中根C．后根D．层次6．具有n个顶点的有向无环图最多可包含（）条有向边。
A．n-1 B．n C．n(n-1)/2 D．n(n-1)7．已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为( ) 。
A．O(1) B．O(m) C．O(n) D．O(m+n)8．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )。
A．s->next=p->next; p->next=s; B．p->next=s; s->next=p->next;C．p->next=s->next; s->next=p; D．s->next=p; p->next=s->next;9．假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。
武夷学院期末考试试卷（ 09级计算机科学与技术专业2010 ～2011 学年度第 1 学期） 课程名称 数据结构 A 卷 考试形式 闭卷 考核类型 考试 本试卷共 五 大题，卷面满分100分，答题时间120分钟。
一、选择题：（本大题共10小题，每小题2分，共20分）1． 某内排序方法的稳定性是指( )。
A ．该排序算法不允许有相同的关键字记录 B ．该排序算法允许有相同的关键字记录 C ．平均时间为0（n log n ）的排序方法 D ．以上都不对2．下面程序段的时间复杂度为( )。
for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i ，j]=x;}A.O (1)B.O (log 2n )C.O (n )D.O (n 2)3．非空的循环单链表head 的尾结点p 满足( )。
A.p->next=head ；B. p->next=NULL ；C.p =NULL ；D. p->next->next =head ；4．设栈s 和队列Q 的初始状态为空， 元素b 1 ，b 2， ，b 3 ， b 4 ， b 5 和b 6 依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是b 2 ，b 4 ，b 3 ，b 6 ，b 5 ，题号 一二三四五六七八总分 复核人得分得分 评卷人………………密……………………封…………………………装…………………订………………………线………………………系别 专业（班级） 姓名 学号b 1 ，，则栈S的容量至少应该是()。
A. 3B. 4C. 5D.其它5．表头和表尾均为空表的广义表是()。
A.()B.(())C.((()))D.(()，())6.下列二叉排序树中，满足平衡二叉树定义的是()。
A ． B.C. D.7．二维数组A的成员是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从1到8，列下标j的范围从1到10，若A按行优先方式存储，起始地址为SA，那么元素A[8][5]的起始地址为()。
2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案1 (2)试题1答案 (7)《数据结构》期末考试试题及答案2 (9)试题2答案 (14)《数据结构》期末考试试题及答案3 (16)试题3答案 (21)《数据结构》期末考试试题及答案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(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
数据结构期末考试试题(含答案)C.{100,98,85,77,80,60,82,40,20,10,66} 答：C。
10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为a。
A.∑(wi/2li)B.∑(wi/li)C.∑(wi/2li-1)D.∑(wi/li-1)答：A。
2005-2006学年第二学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上。
每张答题纸上需写清楚姓名、班号和学号，并在上面写上题目的序号。
一、单项选择题（每小题2分，共20分）1.数据的运算效率与采用何种存储结构有关。
因此，选项A是正确答案。
2.链表不具备的特点是可随机访问任一结点。
参见本节要点3.因此，选项A是正确答案。
3.在顺序表中删除一个元素的时间复杂度为O(n)。
因此，选项C是正确答案。
4.具有随机存取功能的线性表存储结构是顺序表。
因此，选项D是正确答案。
5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是dceab。
因此，选项C是正确答案。
6.循环队列qu的队空条件是qu.rear==qu.front。
因此，选项D是正确答案。
7.两个串相等必有串长度相等且串中各位置字符均对应相等。
因此，选项B是正确答案。
8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是21,32,46,40,80,69,90,94.因此，选项C是正确答案。
9.以下序列不是堆（大根或小根）的是{100,98,85,77,80,60,82,40,20,10,66}。
因此，选项C是正确答案。
10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为∑(wi/2li)。
因此，选项A是正确答案。
C。
{10.20.40.60.66.77.80.82.85.98.100}D。
《数据结构》期末考题(doc 8页)西南财经大学2007 － 2008 学年第二学期统计专业本科 2007、2006级（二、三年级上学期）学号评定成绩（分）学生姓名担任教师周启海《数据结构》期末考试题(B卷)（下述一—三题全作计100分，两小时完卷）考试日期：2008. 12 . 24试题全文：遵守考场纪律，防止一念之差贻误终生。
一、判断题(每小题5分，共10分)1. “广义表”，难用顺序存储结构来描述。
答：2. 已知排序所采用的数据结构、算法思想、语言环境等均相同。
如果对同一组待排序数据，则其递增序排序算法与递减排序算法的运行时间通常不同。
答：二、简答题(每小题5分，共60分)1. 有人说：“学习《数据结构》课程的关键，可概括为——什么是‘数据结构’？有哪些‘数据结构’？各种‘数据结构’特点如何？（所论问题）该用何种‘数据结构’？”这种说法错吗？为什么？答：5. “二叉树”的存储结构，虽然既可采用顺序存储结构（例如数组），也可采用非顺序存储（例如链表）。
但为什么说“非完全二叉树，不宜采用顺序存储结构”？答：6. 设计××××航空公司××航班的“飞机乘客票务管理程序”时，最适宜采用的数据结构是什么？为什么？答：7．现有实现同一功能的三个算法A1，A2和A3，且已知其时间复杂度顺次为Tl=O(2n)，T2=O(n2)，T3=O(n log n)。
请仅就其时间复杂度，给出各算法优化程度递增的顺序，并说明理由。
答：8. 已知有 5 个元素的入栈次序为“A，B，C，D，E”。
现要求第一个出栈元素为C、第二个出栈元素为D，而其余栈元素仍须保留在此栈中。
请说明相关栈及其元素的弹出与压入操作处理过程。
答：9. 已知二叉树含三个结点A、B、C，请给出以B为根结点的二叉树所有形态。
答：10. 设二维数组A[10][8]的每个数组元素占四个存储单位，且第一个元素A[1][1]的存储地址为1000。
2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（A 卷） 答案与评分标准 年级：07级 专业： 班级： 学号： 姓名： 题号 一 二 三 四 五 六 总分 签名 得分 注：1、共100分，考试时间120分钟。
2、此试卷适用于计算机科学与技术本科、信息管理与信息系统专业。
一 得 分 阅卷教师 2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号的总称 ）。
2．抽象数据类型是指一个（ 数学模型 ）以及定义在该模型上的一组操作。
3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与（ 表长和该元素在表中的位置 ）有关。
4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ 108 ）。
5．循环队列的引入是为了克服（ 假溢出 ）。
6．head(tail(head(((a ，b)，(c ，d)))))= b 。
7．已知一棵完全二叉树共有768个结点，则该树中有（ 384 ）个叶子结点。
8．某二叉树的先序遍历序列是8，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（2，4，3，1，7，6，5，9，11，10，8）。
9．有向图G 用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的（ 出度 ）。
10．对n 个待排序记录序列进行快速排序，其最坏时间复杂度为（ O （n 2） ）。
二 得 分 阅卷教师 2分，共10分） 1．算法是指 （ A ） A ．对特定问题求解步骤的一种描述，是指令的有限序列 B ．计算机程序 C ．解决问题的计算方法 D ．数据处理 ——————————————装————————————————订————————————————线————————————2．若某线性表中最常用的操作是取第i个元素和查找第i个元素的前驱，则采用（A ）存储方法最节省时间。
《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。
6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。
7. 树的根结点的度为______，度为0的结点称为______。
8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。
三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。
10. 简述二叉树的遍历方法。
11. 简述图的存储结构及其特点。
四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。
13. 编写一个算法，实现队列的出队操作。
五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。
15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。
答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。
班 姓 学 考试时 考场（教室装 线《数据结构》期末考试试卷(A)一、判断题：（正确者在括号内打“√”，错误者打“×”。
每小题1分，共10分）1．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ ） 2．栈和队列是一种非线性数据结构。
（ ） 3．十字链表是无向图的一种存储结构。
（ ） 4．Hash 表的平均查找长度与处理冲突的方法无关。
（ ） 5．数据元素是数据的最小单位。
（ ） 6．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
（ ） 7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i 层上最多能有2i-1个结点。
（ ） 8．有e 条边的无向图，在邻接表中有e 个结点。
（ ） 9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（ ） 中插入一个新结点,总是插入到叶结点下面。
（ ） 二、选择题：（将每小题正确答案的选项填写在题后的横线上，每小题2分，共20分） x 的赋值语句的频度为___________。
FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A ． O(2n)B ．O(n)C ．O(n 2) D ．O(log2n) 2．下面关于串的的叙述中，哪一个是不正确的？___________。
A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 3．栈和队列的共同特点是___________。
A ．只允许在端点处插入和删除元素B ．都是先进后出C ．都是先进先出D ．没有共同点4．一个向量第一个元素的存储地址是50，每个元素的长度为4，则第5个元素的地址是___________。
A. 70 B. 66 C. 50 D. 785．设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为？___________。
一、（1）简述线性表的两种存储结构的主要优缺点及各自适用的场合。
（2）在折半查找和表插入排序中，记录分别应使用哪种存储结构，并用一句话简述理由。
答：（1）顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除操作将引起元素移动，降低效率。
对于链式存储，元素存储采取动态分配，利用率高。
缺点是须增设指针域，存储数据元素不如顺序存储方便。
优点是插入与删除操作简单，只须修改指针域。
（2）在折半查找中，记录使用顺序存储，可以快速实现中点的定位；在表插入排序中，记录使用静态链表，可以降少移动记录的操作。
二、设T是一棵具有n个节点的二叉树，若给定二叉树T的先序序列和中序序列，并假设T 的先序序列和中序序列分别放在数组PreOrder[1..n]和InOrder[1..n ]中，设计一个构造二叉树T的链式存储结构的算法。
以下为结点类型：typedef struct BiTNode{TElemType data;Struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;解：设T的先序序列和中序序列分别放在数组PreOrder[1..n]和InOrder[1..n ]中，根据先序遍历的特点可知，PreOrder[1]为根节点，设中序序列中InOrder[i]=PreOrder[1]，则在InOrder[i]的左面的InOrder[1..i-1]应为二叉树的左子树，而InOrder[i+1..n]为根的右子树。
相对应的是，在先序序列中根的左子树应为PreOrder[2..i]，而右子树为PreOrder[i+1..n]。
而左子树的根为PreOrder[2]，右子树的根为PreOrder[i+1]。
依次递归，用同样的方法可以确定子树的左子树和右子树，从而逐步确定整个二叉树。
typedef struct BiTNode{TElemType data;Struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;void Create(BiTree T, TElemType PreOrder[], int i1, int j1, TElemType InOrder[], int i2, int j2) {int i=i2;if (i1<=j1){T=(BiTree) malloc(sizeof(BiNode));T→data=PreOrder[i1];T→lchild=NULL；T→rchild=NULL;while (InOrder[i]!=PreOrder[i1]) i++;Create(T→lchild, PreOrder, i1+1, i-i2+i1, InOrder, i2, i-1);Create(T→rchild, PreOrder, i-i2+i1+1, j1, InOrder, i+1, j2);}else T=NULL;}三、用孩子兄弟链表作为树的存储结构，请编写算法计算树的深度。
2008－2009学年第二学期 计算机科学学院《数据结构》期末考试试卷（B 卷）
注：1、共100分，考试时间120分钟。
2分，共20分） 1．数据是对客观事物的符号的表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的（ 符号总称 ）。
2．抽象数据类型是指一个数学模型以及定义在该模型上的一组( 操作 )。
3. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半 ）元素，具体移动的元素个数与表长和( 该元素表中位置 ）有关。
4. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的存储地址是（ 110 ）。
5．循环队列的引入是为了克服（ ）。
6．head(tail(head(((a ，b)，(c ，d)))))= b 。
7．已知一棵完全二叉树共有768个结点，则该树中有（ ）个叶子结点。
8．某二叉树的先序遍历序列是8
，5，1，3，2，4，6，7，10，9，11 ，中序遍历序列是1，2，3，4，5，6，7，8，9，10，11，则其后序遍历序列是（ ）。
9．有向图G 用邻接矩阵存储，其第i 列的所有元素之和等于顶点i 的（ 度数 ）。
10．对n 个待排序记录序列进行快速排序，其最好时间复杂度为（ ）。
2分，共10分） 1．算法是指 （ A ） A ．对特定问题求解步骤的一种描述，是指令的有限序列 B ．计算机程序 C ．解决问题的计算方法 D ．数据处理 2．若某线性表中最常用的操作是取第i 个元素和查找第i 个元素的前驱，则采用（ A ）存储方法最节省时间。
A ．顺序表 B ．单链表 C ．双链表 D ．单循环链表 ——————————————装
————————————————订
————————————————线————————————
3．二叉树的先序序列和后序序列正好相反，则该棵二叉树一定是（D ）的二叉树。
A．空或只有一个结点B．任一结点无左孩子
C．高度等于其结点数D．任一结点无右孩子
4．任何一个无向连通图的最小生成树有（ A ）A．一棵或多棵B．只有一棵C．一定有很多棵D．可能不存在5．二叉排序树中，最小值的结点的（ B ）A．右指针一定为空B．左指针一定为空
D．左、右指针均不为为空
2分，共6分)
数据类型——
数据结构——
队列——
7分，共49分)
1、在什么情况下用顺序表比链表好？
答：
2、简述栈和线性表的差别。
答：
3、设字符串P=‘aabaac’，请求出P的next值和nextval值。
解：
4、有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为
（8、14、10、4、18），请构造相应的哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。
解： 5、已知一棵度为k 的树中有n 1个度为1的结点，n 2个度为2的结点，……，n k 个度为k 的结点，问该树中有多少个叶子结点？ 解： 6、有一图的邻接矩阵如下，用Floyd 算法求各点间最短距离的矩阵序列A 4。
0 2 ∞ ∞ A 0＝ ∞ 0 1 6 5 ∞ 0 4 3 ∞ ∞ 0 解： 7、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：
——————————————装
————————————————订
————————————————线———————————
2分，共10分）
已知L是带头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a、删除P结点的直接后续结点的语句序列是：
b、删除P结点的直接前驱结点的语句序列是：
c、删除P结点的语句序列是：
d、删除首元结点的语句序列是：
e、删除尾元结点的语句序列是：
（1）P=P->next; （2）P->next=P;
（3）P->next=P->next->next; （4）P=P->next->next;
（5）while(P!=Null) P=P->:next;
（6）while(Q->next!=Null){P=Q;Q=Q->next;}
（7）while(P->next!=Q) P=P->next;
（8）while(P->next->next!=Q) P=P->next;
（9）while(P->next->next!=Null) P=P->next;
（10）Q=P; （11）Q=P->next;
（12）P=L; （13）L=L->next;
（14）free(Q);
六、程序设计题(共5分)
试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表做存储结构。
且树中结点的关键字均不同。
解：。
