2010数据结构期末试卷A

期末数据结构试题及答案期末数据结构试题（Ａ）参考答案班别学号姓名成绩⼀、单项选择（每⼩题2分，共24分）1.若某线性表的常⽤操作是取第i个元素及其前趋元素，则采⽤( A )存储⽅式最节省时间A.顺序表B.单链表C.双链表D.单向循环2.串是任意有限个( B )A.符号构成的序列B.字符构成的序列C.符号构成的集合D.字符构成的集合3.设矩阵A(aij,1<=i,j<=10)的元素满⾜:aij<>0(i>=j,1<=i,j<=10),aij =0 (i若将A的所有⾮0元素以⾏为主序存于⾸地址为2000的存储区域中，每个元素占4个单元,则元素A[59]的⾸地址为( C )A.2340B.2336C.2220D.21604.如果以链表作为栈的存储结构,则退栈操作时( D )A.必须判别栈是否满⼲B.对栈不作任何判别C.判别栈元素的类型D.必须判别栈是否空5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执⾏出队操作的语句为( A )A.front=(front+1)%(m+1)B.front=(front+1)% mC.rear=(rear+1)% mD. front=front+16.深度为6(根的层次为1)的⼆叉树⾄多有( B )结点A.64B.63C.31D.327.将含100个结点的完全⼆叉树从根这⼀层开始，每层从左⾄右依次对结点编号，根结点的编号为1。

编号为47的结点X的双亲的编号为( C )A.24B.25C.23D.2⽆法确定8.设有⼀个⽆向图G=(V,E)和G'=(V',E')，如果G'为G的⽣成树，则下⾯不正确的说法是( D)A.G'为G的⼦图B.G'为G的⼀个⽆环⼦图C.G'为G的极⼩连通⼦图且V'=VD.G'为G的连通分量9.⽤线性探测法查找闭散列上，可能要探测多个散列地址，这些位置上的键值( D )A.⼀定都是同义词B.⼀定都不是同义词C.都相同D.不⼀定都是同义词10.⼆分查找要求被查找的表是( C )A.键值有序的链接表B.链接表但键值不⼀定有序表C.键值有序的顺序表D.顺序表但键值不⼀定有序表11.当初始序列已经按键值有序，⽤直接插⼊法对其进⾏排序，需要⽐较的次数为( B )A. n2B. n-1C. log2nD. nlog2n12.堆是⼀个键值序列{K1,K2,...,Ki,...,Kn},对i=1,2,...,└ n/2 ┘，满⾜( A)A. Ki<=K2i且Ki<=K2i+1(2i+1<=n)B.KiC. Ki<=K2i或Ki<=K2i+1(2i+1<=n)D.Ki<=K2i<=K2i+1⼆、判断题(正确的在括号内打"V",错的在括号内打"X",每⼩题1分，共10分)1.双链表中⾄多只有⼀个结点的后继指针为空( V )2.在循环队列中，front指向队列中第⼀个元素的前⼀位置，rear指向实际的队尾元素，队列为满的条件是front=rear( X)rear=front->next;3.对线性表进⾏插⼊和删除操作时，不必移动结点。

全国2010年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.数据的四种存储结构是( ) A-P3A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( ) D-P26（带尾指针）A.无头结点的单向链表B.带头结点的单向链表C.带头结点的双循环链表D.带头结点的单循环链表3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( )C P22A.head=NULLB.head->next=NULLC.head!=NULLD.head->next!=head4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )DA.n-iB.n-i+lC.n-i+2D.无法确定5.串匹配算法的本质是( ) C P55A.串复制B.串比较C.子串定位D.子串链接6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( ) C P61A.13B.18C.33D.407.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) BA.树中没有度为2的结点B.树中只有一个根结点C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) AA.nB.C. +1D.n/29.在图G中求两个结点之间的最短路径可以采用的算法是( )A P123A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法10.下图G=(V,E)是一个带权连通图，G 的最小生成树的权为( )D P116 A.15 B.16 C.17 D.1811.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) B P108 A.1 2 3 4 5 6 7B.1 4 2 6 3 7 5C.1 4 2 5 3 6 7D.1 2 4 6 5 3 712.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) B P136 A.不稳定的 B.稳定的 C.基于交换的D.基于选择的13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( ) C P198 A.1 B.2 C.3D.414.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) D P17415.若需高效地查询多关键字文件，可以采用的文件组织方式为( ) D P218A.顺序文件B.索引文件C.散列文件D.倒排文件二、填空题（本大题共10小题，每小题2分，共20分）请每小题的空格中填上正确答案。

武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）1. 下列各项中属于逻辑结构的是。

A. 哈希表B. 有序表C. 单链表D. 顺序表2. 以下算法的时间复杂度为。

void fun(int n){ int i=1; while (i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)3. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

A. nB. i-1C. n-iD. n-i+14. 判断带头结点的循环单链表L中只有一个结点的条件是。

A. L==NULLB. L->next==LC. L->next->next==LD. L->next==NULL5. 中缀表达式a*(b+c)-d的后缀表达式是。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd6. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。

A. r-fB. r-f-1C. (r-f)％N+1D. (r-f+N)％N7. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。

若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。

A. 1和5B. 2和4C. 4和2D. 5和18. 稀疏矩阵采用压缩存储后，通常必会失去功能。

A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对9. 一棵有124个叶子结点的完全二叉树，最多有个结点。

A. 247B. 248C. 249D. 25010. n个结点的线索二叉树上含有的线索个数为。

《数据结构》期末考试试题及答案(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<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（ a ）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（ d ）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（ c ）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ a ）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（ a b ）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（ c ）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（ c ）域存储后继结点的地址。

一、（本题10分）（1）简述线性表的两种存储结构的主要优缺点及各自适用的场合。

（2）在折半查找和表插入排序中，记录分别应使用哪种存储结构，并用一句话简述理由。

答：（1）顺序存储是按索引（如数组下标）来存取数据元素，优点是可以实现快速的随机存取，缺点是插入与删除操作将引起元素移动，降低效率。

对于链式存储，元素存储采取动态分配，利用率高。

缺点是须增设指针域，存储数据元素不如顺序存储方便。

优点是插入与删除操作简单，只须修改指针域。

（2）在折半查找中，记录使用顺序存储，可以快速实现中点的定位；在表插入排序中，记录使用静态链表，可以降少移动记录的操作。

二、（本题10分）一棵二叉树的先序、中序和后序序列分别如下，部分未显示，请画出该二叉树。

先序序列: _ 2 3_5_7 8;中序序列: 3_4 1_7 8 6；后序序列：_ 4 2 _ _ 6 5 1。

答：三、（本题10分）假定用于通讯的电文仅由a 、b 、c 、d 、e 、f 、g 等8个字母组成，字母在电文中出现的频率分别为：0.07、0.19、0.02、0.06、0.32、0.03、0.21和0.10。

试为这些字母设计哈夫曼编码。

答：一种编码如下：a: 0010 b: 10 c:00000 d:0001 e:01 f:00001 g:11 h:0011四、（本题15分）给定下面的带权无向图G ：1）从顶点0开始，请写出深度优先遍历序列和广度优先遍历序列，当有多种选择时，编号小的结点优先。

2）从顶点0开始，使用普里姆算法求出该图的最小生成树，需画出最小生成树的构造过程。

3）有人给出求解最小生成树的另外一种算法：将连通图中的边按其权值从大到小顺序逐个删123 45768厦门大学《＿数据结构＿》课程期末试卷信息科学与技术学院计算机科学系2008年级＿＿＿专业主考教师：陈怡疆 庄朝晖 试卷类型：（A 卷）除直至不可再删，删除要遵循的原则是：保证在删除该边后各个顶点之间应该是连通的。

班 姓 学 考试时 考场（教室装 线《数据结构》期末考试试卷(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 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为？___________。

杭州电子科技大学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的生成树，则下面不正确的说法是_________。

《数据结构》课程期末考试试卷（ A 卷）考核方式：开卷考试日期：2009 年1 月15 日适用专业、班级：08电子商务1、2一、填空题（每空1分，共10分）1．_字节是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2．数据的物理存储结构分为____顺序存储结构____和____链式存储结构______二种。

3．下面程序段的时间复杂度是O（n）_____。

int n=10,sum=0;for(int i=0;i<n;i++)sum+=n;4.栈和队列是操作受限的线性表，队列又称_先进先出_______线性表。

5．若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点，最多有______个结点。

6．每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。

7．在线性表的散列存储中，处理冲突的常用方法有__开放地址法_____________和_______链地址法_________两种。

二、综合运算题（每小题5分，共25分）1．有以下双端链表的图形，要求完成在最后一个结点插入一个新结点的语句，新插入结点为newEntry，其中newEntry中的数据元素值为“kate”。

其中节点定义类型如下：class Entry{Object data;Entry next;public Entry(Object data){this.data = data;}}2．已知一棵二叉树的前序遍历结果为ABDGEFCH，中序遍历的结果为GDBEAFHC，画出该二叉树，并给出后序遍历的结果。

3．将关键码6３，8８，7５，2７，9７，1９，9１，5５，3３依次插入到一棵初始为空的二叉搜索树中，画出对应的二叉搜索树。

4．举例说明clone方法的含义，并对浅克隆与深度克隆进行说明及图示？5．设待排序文件的关键码为（42, 65,80,77,43,55, 2,87,44,60），第一个元素为分界元素（枢轴）进行快速排序（按关键码值递增顺序），请给出第一趟排序后的结果。

专业 班级 姓名 学号注意：吉林财经大学2010-2011学年第一学期期末考试数据结构试卷A使用对象：计算机09级 模块名称：学科基础课学分：4 考试形式：闭卷一、单项选择题(本大题共10题，每小题1 分，共10分) 在每小题列出的四个选项中只有一个选项是正确的，请将正确答案的标号填在括号内。

1.下面程序的时间复杂度为（ ）。

For(i=0 ; i<m ; i++)For(j=0 ; j<n ; j++) A[i][j]=i*j; A . O(m^2) B. O(n^2) C. O(m*n) D.O(m+n) 2.从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较（ ）个元素结点。

A.n/2 B. n C. (n+1)/2 D. (n-1)/2 3.线性表采用链式存储时，其地址（ ）。

A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可以4.设有一个栈，元素的进栈次序为A ，B ，C ，D ，E ，下列（ ）是不可能的出栈序列。

A. E，A ，B ，C ，D B. B ，C ，D ，E ，A C. A ，B ，C ，D ，E D. E ，D ，C ，B ， A5.在一个链队列中，假定front 和rear 分别为队头和队尾指针，则插入*s 结点的操作应执行（ ）。

A. front->next=s; front=s;B. rear->next=s; rear=s;C. s->next=rear; rear=s;D. s->next=front; front=s; 6.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[1..N]A.R[2i]B. R[2i+1]C. R[i/2]D. R[2i-1]7.如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）A.中序B.前序C.后序D.层次序8.已知10个数据元素（50、30、15、35、70、65、95、60、25、40），按照依次插入结点的方法生成一棵二叉排序树后，在查找成功的情况下，查找每个元素的平均比较次数为( )A. 2.5B. 3.2C. 2.9D. 2.79.对于一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。

武夷学院期末考试试卷（ 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]的起始地址为()。

A．SA+292 B．SA+296 C．SA+300 D．SA+3048．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()。

数据结构与算法A 卷答案一、选择题（本题共20小题，每题2分，共40分）二、分析运算题（本题共6小题，每题6分，共36分）(1) 如果输入序列为6 5 4 3 2 1,试问能否通过栈结构得到以下两个序列3 4 6 5 2 1和2 3 4 1 5 6;请说明为什么不能或如何才能得到 输出序列2 3 4 1 5 6可以得到（2分） 输出序列3 4 6 5 2 1不能得到（2分），其理由是，输出序列中间两元素是6 5，前面2个元素（3 4）得到后，栈中元素剩6 5，且5在栈顶，不可能栈底元素6在栈顶元素5之前出栈(2分)。

(2) 请写出图中二叉树的前序(先序)和中序遍历序列。

①前序(先序)：ABDCEF （3分） ②中序：DBAECF （3分）(3) 算术表达式如下：a*(b+c)-d ① 用二叉树表示算术表达式 ② 写出后序（后缀）表达式（3分）②后序（后缀）表达式：abc+*d-（3分）(4) 请写出无向图中顶点a-f 的度 a:3（1分） b:2（1分） c:1（1分） d:2（1分） e:4（1分） f:2（1分）(5) 给定元素序列：（50，25，80，20，76，93），画出按照该序列构造的二叉排序树(必须画出二叉排序树的建树过程)。

每个结点1分(6) 下面的邻接表表示一个给定的无向图 ① 请根据邻接表画出无向图② 给出从顶点v1开始, 根据邻接表对图用深度优先搜索法进行遍历时的顶点序列；③ 给出从顶点v1开始, 根据邻接表对图用广度优先搜索法进行遍历时的顶点序列。

（2分）②深度序列：V1 V2 V5 V3 V4 V6 （2分） ③广度序列：V1 V2 V3 V4 V5 V6 （2分）50 2580769320三、程序填空题（本题共5空，每空2分，共10分）①p->next（2分）②malloc（2分）③data（2分）④s->next = p->next（2分）⑤p->next = s（2分）四、算法设计题（本题共1小题，每题14分，共14分）1. 如果通讯字符a，b，c，d出现频度分别为7，5，2，4①某同学设计了如下程序，请根据程序画出对应的二叉树，计算所画出的二叉树的带权路径长度（必须写出计算过程，否则不给分）；②请画出赫夫曼（哈弗曼）树(必须画出赫夫曼树的建树过程)；③计算它的带权路径长度（必须写出计算过程，否则不给分）④根据赫夫曼树，用if-else语句修改①中的程序，写出最佳判定算法。

《数据结构》期末考试试卷（ A ）一、选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据B.数据元素C.数据结构D.数据类型2．栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100D. 1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA. 2h B .2h-1C. 2h+1D. h+1软件开发网8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

下列结论哪个正确？AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2D. 411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点软件开发网12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41B.23和39C.15和44D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。

数据结构期末考试试卷（A卷）第一学期开课单位：软件学院，考试形式：闭、开卷，允许带入场科目：数据结构班级：软件工程姓名：学号：题序一二三四五六七八九总分得分评卷人I. 基本概念部分（共60分）1 下图所示是单链表结点的插入过程，在fence结点后面插入一个值为10的ltmp结点，已知fence->next是指向fence的后继结点，请把这一插入过程用代码表示出来：(6分)这一过程的代码：ltmp->next = fence->next;fence->next = ltmp;2 下图所示是双链表结点的删除过程，在fence结点后面删除一个值为23的结点，已知fence->next是指向fence的后继结点，fence->prev是指向fence的前驱结点，ltmp是一个值为NULL的链表结点指针，请把这一删除过程用代码表示出来：(8分)这一过程的代码：ltmp = fence->next;fence->next = ltmp->next;ltmp->next->prev = fence;3 画出下图中的BST加上值5以后的形状。

(6分)4 画出下图所示图的相邻矩阵表示(假设下面的表格是一个二维数组,请在表格中填入正确的数值)。

(8分)1 2 3 4 5 61 10 20 22 103 53 3 154 205 11 105 15 11 36 2 10 35 给出下图从顶点1开始的DFS 树。

(8分)深度优先搜索（DFS ）：从底到高，从小到大 广度优先搜索（BFS ）：直接在下面的顶点中画出来即可：6 给出下图从顶点3开始使用Prim （普里姆）算法时的最小支撑树（最小生成树）。

(8分)32154 32154直接在下面的顶点中画出来即可：24 16357 起泡排序函数的算法如下：(8分)void bubsort(int A[], int n){int tmp;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){if(A[i] > A[j]){tmp = A[i];A[i] = A[j];A[j] = tmp;}}//外层循环,打印一下中间结果for(int k = 0; k < n; k++) printf(" %d",A[k]);printf("\n");}}对数组int A[] = { 9, 12,3,7,90,15};应用上面的排序算法进行排序的部分中间打印结果如下，请补充使之完整：8 给出从下图的最大值堆中删除最大元素后得到的堆。

武夷学院期末考试试卷（ 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]的起始地址为()。

北京电子科技学院2009～2010学年第二学期0821~0822 班 数据结构 期 末 考 试 试 卷（闭卷）（Ａ卷）一、选择题（每小题2分，共10分）1．在数据结构中，从逻辑上可以把数据结构分为 。

A ．动态结构和静态结构 B ．紧凑结构和非紧凑结构 C ．线性结构和非线性结构 D ．内部结构和外部结构2．对于顺序表的优缺点，以下说法错误的是。

A ．无需为表示结点间的逻辑关系而增加额外的存储空间 B ．插入和删除操作较方便C ．可以方便的随机存取表中的任一结点D ．由于顺序表要求占用连续的空间，存储分配只能预先分配3．设有一顺序栈已经含有3个元素，如下图所示，元素a4正等待入栈。

以下序列中不可能出现的出栈序列是 。

A ．a3, a2, a4, a1B ．a3, a1, a4, a2C ．a3, a4, a2, a1D ．a4, a3, a2, a1专业________________学号__________________姓名__________________班级____________________密 封 线4．对采用折半查找法进行查找操作的查找表，要求按方式进行存储。

A．顺序存储B．链式存储C．顺序存储且结点按关键字有序D．链式存储且结点按关键字有序5．以下不属于选择排序方法的是。

A．冒泡排序B．树形选择排序C．堆排序D．直接选择排序二、填空题（每小题2分，共10分）1．数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容：，和对数据施加的操作。

2．下列程序段的时间复杂度是。

s=0;for (i=1;i<=n; i++)for (j=1;j<=i; j++)s=s+B[i,j];sum=s;3．在具有n个单元的循环队列中，队满时共有个元素。

4．一个n n的对称矩阵，如果以行或者列为主序存入内存，则其需要的存储空间容量为。

5．广义表运算式Head(Tail( (a,b,c),(x,y,z) ) ) 的结果为。