13级数据结构期中试卷(打印)

数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序3. 在二叉树中，度为2的节点最多有多少个子节点？A. 1B. 2C. 3D. 44. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 树形结构法5. 以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 克鲁斯卡尔算法6. 栈的特点是？A. 后进先出B. 先进后出C. 先进先出D. 后进后出7. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于它的根节点的值B. 右子树上所有节点的值大于它的根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等8. 在数据库中，索引的作用是什么？A. 增加数据存储空间B. 提高数据检索效率C. 降低数据插入速度D. 减少数据存储量9. 以下哪个不是图的存储结构？A. 邻接矩阵B. 邻接表C. 树形结构D. 边列表10. 递归算法的基本思想是什么？A. 将问题分解为更小的子问题B. 重复执行相同的操作C. 将问题转化为非递归形式D. 避免使用循环结构二、填空题（每题2分，共20分）1. 在数据结构中，______是一种特殊的线性表，只允许在一端进行插入和删除操作。

2. 排序算法中，______排序的时间复杂度为O(n^2)，适用于小规模数据的排序。

3. 在图的表示中，______矩阵可以有效地表示稠密图。

4. 哈希表中，______是指两个关键字通过哈希函数得到同一个哈希地址。

5. 栈和队列的主要区别在于，栈是______，而队列是先进先出。

6. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。

11-12学年2学期电⼦信息⼯程《数据结构》期中试卷11-12学年2学期电⼦信息⼯程《数据结构》期中试卷答题纸上只写班级姓名学号及每题答案。

1、单项选择题(本⼤题共30⼩题，每⼩题1分，共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其代码填写在题后的括号内。

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

1.数据的不可分割的最⼩标识单位是（）A.数据项B.数据记录C.数据元素D.数据变量2.for(i=0;ifor(j=0;jc[i][j]=0;for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];上列程序的时间复杂度为（）A.O(m+n×t)B.O(m+n+t)C.O(m×n×t)D.O(m×t+n)3.若线性表最常⽤的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储⽅式是（）A.单链表B.双链表C.单循环链表D.顺序表4.设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为（）A.p—>next=p—>next—>nextB.p=p—>nextC.p=p—>next—>nextD.p—>next=p5.向⼀个栈顶指针为hs的链栈中插⼊⼀个*s结点时，应执⾏的操作为（）A.hs—>next=s;B.s—>next=hs;hs=s;C.s—>next=hs—>next;hs—>next=s;D.s—>next=hs;hs=hs—>next;6.设循环队列的元素存放在⼀维数组Q[0‥30]中，队列⾮空时，front指⽰队头元素的前⼀个位置，rear指⽰队尾元素。

如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）A.Q[4]D.Q[15]7.定义⼆维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以⾏序为主序的存储⽅式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储⽅式下，该元素的存储地址为（）A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n个结点的⼆叉树，拥有指向孩⼦结点的分⽀数⽬是（）A.n-1B.nC.n+1D.2n9.对⼀棵有100个结点的完全⼆叉树按层序编号，则编号为49的结点，它的左孩⼦的编号为（）A.99B.98C.97D.5010.有m个叶⼦结点的哈夫曼树，其结点总数是（）A.2m-1B.2mC.2m+1D.2(m+1)11.有n个结点的⽆向图的边数最多为（）A.n+1B.n(n-1)/2C.n(n+1)D.2n(n+1)12.设图的邻接矩阵为，则该图为（）A.有向图B.⽆向图C.强连通图D.完全图13.⼆分查找算法的时间复杂度是（）B.O(nlog2n)C.O(n)14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插⼊结点的⽅法⽣成⼀棵⼆叉排序树，则该树的深度为（）A.4B.5C.6D.715.采⽤排序算法对n个元素进⾏排序，其排序趟数肯定为n-1趟的排序⽅法是（）A.插⼊和快速B.冒泡和快速C.选择和插⼊D.选择和冒泡16.从逻辑上可以把数据结构分为（）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、⾮线性结构D.初等结构、构造型结构17.关于算法的描述，不正确的是（）A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执⾏时间的⼀个上界C.健壮的算法不会因⾮法的输⼊数据⽽出现莫名其妙的状态D.算法的优劣与算法描述语⾔⽆关18.在单链表中，存储每个结点需要有两个域，⼀个是数据域，另⼀个是指针域，指针域指向该结点的（）A.直接前趋B.直接后继C.开始结点D.终端结点19.将两个各有n个元素的有序表合并成⼀个有序表，其最少的⽐较次数为（）A.nB.2n-1C.2nD.n220.栈和队列共同具有的特点是（）A.都是先进后出B.都是先进先出C.只允许在端点进⾏操作运算D.既能先进先出，也能先进后出21.若⽤⼀个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13(总分：66.00，做题时间：90分钟)一、综合题(总题数：4，分数：12.00)1.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

【北京工业大学1998五(10分)】__________________________________________________________________________________________正确答案：(设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00）(1).T树的最大可能深度Kmax=?最小可能深度Kmin=?__________________________________________________________________________________________ 正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。

T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。

)(2).T树中共有多少非叶结点?__________________________________________________________________________________________ 正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。

)(3).若叶结点的权值分别为1，2，3，4，5，6。

请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。

【北京邮电大学1992一、3(15／3分)】__________________________________________________________________________________________正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51。

数据结构13级期中考试参考答案五邑大学试卷（期中参考答案）课程：数据结构学期： 2021 至 2021 学年度第 2 学期一、单项选择题（10小题，每小题2分，共20分）1．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n ，则第i个输出元素是（ D ）。

A．不确定 A．顺序表 A． 7B．n-i B．栈C．n-i-1 C．队列D．n-i+1 D．链表2．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。

3．设有6个结点的无向图，该图至少应有（ C ）条边才能确保是一个连通图。

B. 6C. 5D. 4D．散列存取 D．O(nlog2n)4．线性表的顺序存储结构是一种（ A ）的存储结构。

A．随机存取 A．O(1)B．顺序存取 B．O(n)C．索引存取 C．O(n2)5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ C ）。

6．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A ）。

A．肯定不发生改变 C．不能确定B．肯定会发生改变 D．有时发生变化B．从源点到终点的最短路径 D．最短的回路7．关键路径是AOE网中（ A ）。

A．从源点到终点的最长路径 C．最长的回路 for(i=0; i B． O(n)C． O(log2n) C．树形结构 D． O(n2) 8．下列算法的时间复杂度是（ B ）。

9．下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ A ）。

A．集合 B. 线性结构 D. 图状结构 10．在单链表中，若p所指结点不是尾结点，在p之后插入s所指结点的操作是（ B ）。

A．s->next=p; p->next=s C．s->next=p->next; p=s; 二、填空题(10小题，19个空，每空2分，共38分) 1．表示有100个顶点，133条边的无向图的邻接矩阵有（266）个非零矩阵元素。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

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

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

A. SA+141B. SA+180C. SA+186D. SA+2107、用无回溯的模式匹配法（KMP法）求串“ababab”的next[j]的值为（）。

A. 010101B. 011221C. 011233D. 011234C.可链接存储D. 数据元素可以是多个字符8、链表不具有的特点是（）。

A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比9、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是（）。

A. A*B+C/D-E+FB. AB*C+D/E-F+C. ABC+*DE-F+/D. ABCDEF*+/-+10、已知输入序列为abcd，经过输出受限的双端队列后能得到的输出序列是（）。

A. dacbB. cadbC. dbcaD. 以上都不是二、填空题（每空2.5分，共25分）【得分：】1、有如下递归函数：int func(int n){if(n<2) return(n);else return(func(n-1)+func(n-2));}执行语句printf(“%d\n”,func(4));的结果是。

2、若一个算法中的语句频度之和为T(n)=3n+n*log2n+n2，则算法的时间复杂度为O(_ ___)。

3、不带头结点的单链表head为空的条件是。

4、假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度和队头指针值分别为13和17，则当前队尾指针的值为。

5、将一个A[15][15]的对称矩阵采用只存储下三角中元素的压缩存储（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A中元素[3][7]在B 数组中的位置为。

6、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是。

7、已知L是带头结点的非空单链表，删除首元结点的三条语句为：P=L->next;;free(P);8、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，第2页共7页第 3 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写此处不能书写插入一个元素所需移动元素的平均次数为： ；删除一个元素需要移动的元素个数为： 。

《数据结构》期中试卷专业________ 学号_________ 姓名________ 成绩_______一、选择题（本大题共50小题，每小题2分，共100分）1. 若广义表K满足head(K)=tail(K),则K为 ( )A.( )B.( ( ) )C. ( () ),( () )D.( (),(),() )2.若要求尽可能快地对实数数组进行稳定的排序，则应选( )A.快速排序B.堆排序C.归并排序D.基数排序3. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（）次关键码比较。

A.2B.3C.4D.54．对包含N个元素的散列表进行查找，平均查找长度( ）A.为 O(log2N)B.为O(N)C.不直接依赖于ND.上述三者都不是5.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，16．下面关于图的存储的叙述中，哪一个是正确的。

（）A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关7. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( )A.前序遍历B.后序遍历C.中序遍历D.层次遍历8.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是( )A.小于B.大于C.等于D.不小于9.下面关于B-树和B+树的叙述中，不正确的是 ( )A. B-树和B+树都是平衡的多分树B. B-树和B+树都是可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索10. 给定下列有向图和初始结点V1,按深度优先遍历的结点序列为( )A.V1，V2，V4，V5，V3B.V1，V3，V4，V5，V2C.V1，V2，V5，V3，V4D.V1，V2，V3，V4，V511. 在数据结构中，从逻辑上可以把数据结构分成（）。

《数据结构》期中测试班级：姓名：学号：一、填空题：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所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

2013年1月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331考生答题注意事项：1.本卷所有试卷必须在答题卡上作答。

答在试卷和草稿纸上的无效。

2.第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3.第二部分为非选择题。

必须注明大、小题号，使用0.5毫米黑色字迹笔作答。

4.合理安排答题空间，超出答题区域无效。

选择题部分一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

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

1．数据的逻辑结构可以分为A．动态结构和静态结构 B.顺序结构和链式结构C．线性结构和非线性结构 D.简单结构和构造结构2．线性表是一个有限序列，组成线性表的基本单位是A．数据项 B.数据元素C．数据域 D.字符3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可．．能．的出栈序列是A．dcba B.cbdaC．cadb D.cdba4．稀疏矩阵的三元组表是A．顺序存储结构 B.链式存储结构C．索引存储结构 D.散列表存储结构5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是A．5 B.6C．7 D.86．下列编码集合中，属于前缀编码的一组是A.{11,10,001,101,0001}B.{00,010,0110,1000}C.{11,01,001,0101,0001}D.{0,10,110,1011}7.如题7图所示二叉树的中序序列为A．ACDBB．DCBAC．CDBAD．ABCD题7图8．有向图中所有顶点入度之和与所有顶点出度之和的比是A．1/2 B.1C．2 D.49．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是A.eB.2eC.n2-2eD.n2-e10.n个顶点的无向连通图，其生成树的边数为A.n-lB.nC.n+lD.nlogn11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为A．2 B.3C．4 D.512．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是A.(13,44,55,26,8,29)B.(13,26,55,44,8,29)C.(8,13,26,29,44,55)D.(29,26,8,44,55,13)13．采用分块查找时，要求数据A．块内有序 B.分块有序C．分块无序 D.每块中数据个数必须相同14.下列关于散列函数的说法正确的是A．散列函数越复杂越好B.散列函数越简单越好C．用除余法构造的散列函数是最好的D.在冲突尽可能少的情况下，散列函数越简单越好15.下列关于m阶B树的叙述中，错误．．的是A．每个结点至多有m棵子树B.每个结点至多有m-1个关键字 C ．所有的叶结点均在同一层上 D.根结点至少有/2m ⎡⎤⎢⎥棵子树非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。

满分100分，共20道选择题，每题5分。

请在60分钟内完成。

C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。

3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。

线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。

5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。

6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。

2014-2015学年第二学期《数据结构与算法》期中考试学号：姓名：一、写语句1.设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。

2.设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作3. 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入s结点的C语言描述语句。

4. 一线性表存储在带头结点的双向循环链表中，L为头指针。

如下算法：（1）说明该算法的功能。

（2）在空缺处填写相应的语句。

void unknown (BNODETP *L){ …p=L->next; q=p->next; r=q->next；while (q!=L){ while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；(1) ______；q->next=p->next；q->prior=p；(2) ______；(3) ______；q=r；p=q->prior；(4) ______；} }二、写算法1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；(2) 在单链表将比正整数x小的数按递减次序排列；(3) 将正整数（比）x大的偶数从单链表中删除。

2. 设键盘输入n个英语单词，输入格式为n, w1, w2, …,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（1）如果单词重复出现，则只在链表上保留一个。

1．评价算法优劣的基本标准有哪些？请就每一项给出简短说明。

答：（1）正确性：对输入的合法数据（包括边界情况），都能有正确的输出结果。

（2）健壮性：对输入的非法数据，算法能适当地做出反应或进行处理，而不是产生莫名其妙的输出结果。

（3）可读性：有助于人对算法的理解，易于发现错误，便于调试和修改。

（4）效率与低存储量需求：效率和存储量需求分别指算法执行所需要的时间和最大存储空间。

2．已知一棵二叉树的中序和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，（1）画出这棵二叉树，对这棵二叉树的构造过程给出一个简短说明；（2）将这棵二叉树理解为“孩子-兄弟法”表示的森林，画出这个森林。

答：（1）构造出的二叉树如图1所示：图1构造过程说明：①后序序列的最后一个元素为A, 得知二叉树的根为A；②在中序序列中找到树根A, A左侧的部分GLDHBEI为左子树的中序序列，A右侧的部分CJFK为右子树的中序序列。

并得知左子树7个节点，右子树4个节点；③后序序列的前7个节点LGHDIEB是左子树的后序序列，后续序列的后4个节点JKFC是右子树的后序序列；④根据中序GLDHBEI后序LGHDIEB求左子树，根据中序CJFK后序JKFC 求右子树。

依此类推，便可唯一构造出此二叉树。

（2）“孩子-兄弟表示法”，又称二叉链表表示法，链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，一棵二叉树与森林一一对应，该森林如图2所示：图23．字符A，B，C，D，E，F，G的使用频度分别是15，8，10，21，6，19，3，写出A，B，C，D，E，F，G的Huffman编码，列出编码过程，解释Huffman 有什么优点。

解：编码过程如下：各字符编码为字符 A B C D E F G编码011 110 010 00 1111 10 1110优点：Huffman编码为前缀码，它根据结点出现的频度由低到高编码，则可以使频度较高的结点有尽可能短的编码，从而使整个发送文件的总编码长度尽可能短。

北京经济技术职业学院2013－2014学年第一学期12级计算机应用技术专业《数据结构构》课程期中考试试卷专业：班级：姓名：学号：得分：注意事项：1.共6页，用钢笔或圆珠笔答卷。

2.闭卷.3.总分：100分，考试时间：100分钟试题的所有答案都要写在试卷后附的答题纸上，不按要求做的一律不能得分。

一、单项选择题（本大题共15小题，每小题2分，共30分）。

1. 自定义标识符由字母、数字或下划线组成，且第一个字符必须是( )。

A.数字B.字母或数字C.数字或下划线D.字母或下划线2. 关于C语言程序描述正确的是( )。

A.函数必须要有return语句B.主函数必须位于程序的开头C.程序中每行只能写一条语句D.一个程序中只能有一个主函数3. 关于for(表达式1；表达式2；表达式3)，叙述正确的是( )。

A.表达式1不可以缺省B.表达式2不可以缺省C. 三个表达式都可以缺省D.表达式3不可以缺省4. 下列为C语言关键字（或称作保留字）的是( )。

A.realB.longC.pointerD.integer5. 在循环结构中，continue语句的作用是( )。

A.继续执行本次循环B.提前退出多重循环C.提前结束本次循环D.提前退出本重循环6. 数组定义及初始化正确的是( )。

A.char a[5]={}；B.int a[5]={0，1，2，3，4，5}；C.char a={"string"}；D.char a[]={＇0＇，＇1＇，＇2＇，＇3＇，＇4＇，＇5＇}；7. 正确表示数学关系式x≥y≥z的C语言表达式是( )。

A.x>=y>=zB.(x>=y)&&(y>=z)C.(x>=y)&(y>=z)D.(x>=y)||(y>=z)8. 设int m；，与while(!m)等价的是( )。

A.while(m!=0)B.while(m==1)C.while(m==0)D.while(m!=1)9、设char *sl="12345",*s2="1234"；，执行语句printf("％d\n"，strlen(strcpy(sl，s2)))；后的输出结果是( )。