2010年数据结构期中考试试卷及答案

一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。

A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。

A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。

A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。

D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。

A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。

A )。

A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。

一、判断题：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、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

2010年数据结构期中考试试卷及答案《数据结构》期中试卷（2009级） 2010-2011学年第⼀学期姓名：学号：成绩：⼀、选择题：（每⼩题2分，共20分）1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪⼀个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 62.在⼀个有125个元素的顺序表中插⼊⼀个新元素并保持原来顺序不变，平均要移动（）个元素。

A．8 B. 62.5 C. 62 D. 73. 已知⼴义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原⼦项e的运算是：( )A.head(tail(A))B.head(tail(tail(A)))C.head(head(tail(tail(A))))D.head(tail(head(tail(A))))4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则⼊队时的操作为（）。

A. front=( front +1) mod (m+1)B. rear=(rear+1) mod (m+1)C. front=( front +1) mod mD. rear=(rear+1) mod m5. 在双向循环链表中,在p指针所指向的结点前插⼊⼀个指针q所指向的新结点,其修改指针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。

A．p->llink=q；q->rlink=p；p->llink->rlink=q；q->llink=q；B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink；C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q;D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q；6. ⼀棵完全⼆叉树上有1001个结点，其中叶⼦结点的个数是（）。

数计系08级网工《数据结构》期中考试题（2009－2010学年度上学期）试卷类别：闭卷考试时间：120分钟班级座号姓名一、选择题（共20分，每题2分）1．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2．在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)3．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4．对于栈操作数据的原则是（）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序5．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)6．串的长度是指（）A ．串中所含不同字母的个数B ．串中所含字符的个数C ．串中所含不同字符的个数D ．串中所含非空格字符的个数7．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）A. p->next=hB. p->next=NULLC. p->next=hD. p->data=-18．判定一个循环队列Q （存放元素的位置为0～MAXQSIZE-1）队满的条件是（ ）A ．Q.front==Q.rearB ．Q.front==(Q.rear+1)%MAXQSIZEC ．Q.front+1==Q.rearD ．Q.rear==(Q.front+1)%MAXQSIZE9．在C 语言中，将一个A[15][15]的下三角矩阵，按行优先存入一维数组B[120]中，A 中元素A[6][5]在B 数组中的位置k 为（ ）A ．19B ．26C ．21D ．1510．已知广义表L=（（x,y,z ），a ，（u ，t ，w ）），从L 表中取出原子项t 的运算是（ ）。

数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。

A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。

A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。

A 、线性表中的数据元素可以是数字、字符、记录等不同类型。

B 、线性表中包含的数据元素个数不是任意的。

C 、线性表中的每个结点都有且只有⼀个直接前驱和直接后继。

D 、存在这样的线性表：表中各结点都没有直接前驱和直接后继。

4、关于单链表的说法，请选出不正确的⼀项( C)。

A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。

A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。

x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。

A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。

T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。

2010年春季学期计算机科学与技术、软件工程、网络工程专业《数据结构》期中考试卷面总分：100分答题时间：120分钟专业年级班级姓名学号说明：一、二题的答案必须写在以下答题卡上，写在别处不得分。

第二题答题卡：一、单项选择题（本大题共15小题，每小题2分，共30分答案写在答题卡上）1、算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档特点2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用链接存储，不必占用一片连续的存储单元。

C．线性表采用顺序存储，便于进行插入和删除操作。

D．线性表采用链接存储，便于插入和删除操作。

3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．带头结点的双循环链表 B．双链表C．顺序表 D．单循环链表4、单链表中，增加一个头结点的目的是为了( ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置C．方便运算的实现 D．说明单链表是线性表的链式存储5、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A. 1，2，4，3B. 2，1，3，4C. 4，3，1，2D. 1，4，3，26、中缀表达式（A+B）*（C-D）/(E-F*G)的后缀表达式是_____；A. A+B*C-D/E-F*GB. AB+CD-*EFG*-/C. AB+C*D-E/F-G*D. ABCDEFG+*-/-*7、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是A. 1B. 3C. 2D. 48、循环队列存储在数组A[0..m]中，则入队时的操作为( )。

A. rear=(rear+1) % (m-1)B. rear=(rear+1) % (m+1)C. rear=(rear+1) % mD. rear=rear+19、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储10、串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？A. 可以顺序存储B. 数据元素是一个字符C. 数据元素可以是多个字符D. 可以链接存储11、对矩阵压缩存储是为了（）。

《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。

数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。

在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。

顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。

在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。

4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。

给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。

5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

在p所指结点后插入s所指结点：4、1。

在p所指结点前插入s所指结点：7、11、8、4、1。

在表首插入s所指结点：5、12。

在表尾插入s所指结点：11、9、1、6。

1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

杭州电子科技大学2010《数据结构》真题及解析一、是非题(每小题2分，共20分)1.线性表的顺序存储结构优于链式存储结构。

2.栈和队列也是线性表。

如果需要，可对它们中的任一元素进行操作。

3.非空广义表的表头和表尾都有可能是原子或广义表。

4.在二叉树的先序遍历序列中，任意-个结点均处在其孩子结点的前面。

5.通常，在二叉树的第i层上有2^i-1个结点。

6.二叉树按某种次序线索化后，任一结点均有指向其前驱和后继的线索指针。

6.赫夫曼树中的结点个数一定是奇数。

8.用邻接矩阵(数组表示法)存储一个图时，所需的存储空间大小与图的边数无关。

9.对于一棵m阶的B-树而言.树中每个结点至多有m个关键字，除根之外的所有非终端结点至少有┌m/2┐个关键字。

10.对于任何待排序序列来说，快速排序均快于冒泡排序。

二、选择题(每小题2分，共20分)1.递归过程可借助于_____转化为非递归过程。

A:线性表 B:队列 C:栈 D:数组2.循环队列用数组A[0..m-1]存放其元素值，设头尾游标分别为front(队头元素的位置)和rear(队尾元素的位置)，则当前队列中的元素个数是_______。

A: rear-front B: rear-front+1C: (rear-front+m)%m D: (rear-front+1+m)%m3.对广义表A=（（a, （6）），(c，（））,d）执行操作gettail(gethead(gettail （A）））的结果是:________。

A:（） B:(()) C:d D:(d)4.对二叉排序树______可得到有序序列。

A:按层遍历 B:前序遍历C:中序遍历 D：后序遍历5.在有n个结点的二叉树的二叉链表表示中，空指针数为________。

A:不定 B: n+1 C:n D：n-16.图示的三棵二叉树中_____为最优二叉树。

A: B: C:7.设无向图G=(V,E)和G=(V′,E′)，若G′是G的生成树，则下面不正确的说法是_________。

安徽大学2010—2011学年第2学期《 数据结构 》考试试卷（B 卷） （闭卷 时间120分钟）考场登记表序号一、填空题（每小题1.5分，共15分） 1．含有36个元素的有序表，进行二分查找时的判定树的深度为 6 。

2．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍。

3． 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 44 。

4．由a ，b ，c 三个结点构成的二叉树，共有 5 种不同形态。

5．二维数组A[0‥5][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[0][5]的存储地址是1000，则A[3][9]的地址是 1088 。

6．若串s=''soft ，则其子串个数是 11 。

7. 设循环队列的空间大小为M ，入队时修改队尾指针rear 的语句为 rear=(rear+1)%M 。

8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中 一半 元素。

9．下列程序段的时间复杂度是 O(m*n) 。

for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]+=5;10. 在数据结构中，与所使用的计算机无关的是数据的 逻辑 结构。

二、单项选择题（每小题2分，共20分）1. 数据结构可以用二元组来表示，它包括（ A ）集合D 和定义在D 上的（ C ）集合R 。

A 、数据元素B 、存储结构C 、元素之间的关系D 、逻辑结构2． 已知L 是一个不带头结点的单链表，p 指向其中的一个结点，选择合适的语句实现在院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------p结点的后面插入一个结点s的操作（B）。

江 西 理 工 大 学 考 试 试 卷试卷编号：1213010547 -B一、 填空题（共38分）1、数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。

（4分）2、在n 个元素的顺序表中插入一个元素，需要最多移动 n 元素，具体移动的元素个数与插入的元素的位子 有关。

（4分）3、从循环队列中插入一个元素时，其操作是先 插入元素 ，后 移动队首指针 。

（4分）4、设S=”h:/美的Mary.doc”，则strlen(s)= 15 , “的”的字符定位的位置为 6 。

（4分）5、一棵深度为4的完全二叉树最少有 7 个分支结点和最少有 8 个叶子。

（4分）6、由下图中的二叉树可以得出其遍历序列：其中先根遍历序列为： ABDGCHKELIFJ 、中根遍历序列为： BCGDAEKHILFJ 、后根遍历序列为： CGDBEKIJFLHA 。

（6分）7、n 个顶点e 条边的图采用邻接表存储，广度优先遍历算班级 学号 姓名法的时间复杂度为O(n+e) ；若采用邻接表存储，该算法的时间复杂度为O(n2) 。

（4分）8、若一个堆栈的输入序列是1,2, …,m-1,m，则输出序列的最后一个元素是1 ，则第i个输出元素是：m-i+1 。

（4分）9、用邻接矩阵存储包含30个顶点和35条边的有向图，则该邻接矩阵中的元素个数为900 ，零元素个数为865 。

（4分）二、应用题（32分）1、若一棵度为m的树中有n(1)个度为1的节点，n(2)个度为2的节点，n(3)个度为3的节点，…，n(m)个度为m的节点，问该树有多少个叶节点？（9分）答：每个度为1的节点有1个子节点，即每个该类节点有1条边连接子节点；每个度为2的节点有2个子节点，即每个该类节点有2条边连接子节点；……;每个度为m的节点有m个子节点，即每个该类节点有m条边连接子节点；每个度为0的节点(叶节点) 有0个子节点，即每个该类节点有0条边连接子节点；设叶节点的个数为n(0),因此该树的边数为:n(1)+2n(2)+…+m*n(m)树中仅有1个根节点，除根节点外，树中每个节点有且仅有1条边与其父节点相连。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头 B．表尾 C．任意位置 D．指定位置2、下述哪一条是顺序存储结构的优点（2）。

A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D． O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

数据结构2010年下学期 考试时间：100分钟 考试形式：闭卷（所有答案写在答题纸上，请在答题纸上注明班级、学号） 一、概念题（每题 2 分，共 24分） 1、从逻辑角度看，数据可归结为四类基本结构：集合、线性结构、 树状结构 和 图状结构 。

2、算法效率度量分析的两个基本指标是 时间复杂度 和 空间复杂度 。

前者是基于算法执行时间的度量，后者是基于算法所需存储空间的度量。

3、线性表顺序存储的特点是：表中相邻的元素a i 和a i+1所对应的存储地址 LOC （a i ）和LOC(a i+1)也是____相邻_____的。

设线性表a 的起始地址为LOC(a 1)，每个数组元素所占用的存储单元数为b ，则表中第i(1≤i ≤n)个元素a i 的存储起始地址LOC(a i )可用如下公式得到__ LOC(a i )_ = LOC(a 1)+(i-1)*b ______。

4、在线性表的存储结构中，顺序表是一个可 随机存取 存取的存储结构，单链表则是一个 顺序存取 存取的存储结构。

5、设单链表的结点数据类型定义和指针变量说明如下 #define DATATYPE2 char typedef struct node { DATATYPE2 data; struct node *next; } LINKLIST; LINKLIST *p,*q,*s; 在一个单链表中，已知q 所指向结点是p 所指向结点的直接前趋结点。

若欲在q 结点和p 结点之间插入一个s 所指向的结点，则可写 q->next=s;s->next=p 6、关于选用顺序表结构或链表结构，在考虑线性表的操作的时间性能时，若线性表上的操作主要是查找、读取而很少做插入和删除操作时，以采用 顺序 表结构为宜。

但是，若线性表需频繁地进行插入和删除操作时，则采用 链表 表结构为宜。

7、如果在待排序的序列中，存在有多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是 稳定 的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。