数据结构期中试卷

数据结构期中考试试卷一、选择题（每题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. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。

第页/共 页 《数据结构》期中考试试卷一、选择题（每题2分，共40分）1．组成数据的基本单位是【 】。

A ．数据项B ．数据类型C ．数据元素D ．数据变量 2．线性表采用链式存储时，结点的存储地址【 】。

A ．必须是不连续的 B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3. 有一个含头结点的单链表，头指针为head ，判断其是否为空的条件为【 】。

A ．head==NULL B ． head->next==NULL C ．head->next==head D ．head!=NULL 4．算法分析的目的是【 】。

A ．辨别数据结构的合理性B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性5．已知指针p 所指结点不是尾结点，若在*p 之后插入结点*s ，则应执行下列哪一个操作？【 】。

A. s->next = p ； p-> next = s ；B. s-> next = p-> next ； p-> next = s ；C. s-> next = p-> next ； p = s ；D. p-> next = s ； s-> next = p ； 6．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可 能出现的出栈序列为【 】。

A ．3，2，6，1，4，5B ．5，6，4，2，3，1C ．1，2，5，3，4，6D ．3，4，2，1，6，5 7．一个元素进入队列的时间复杂度是【 】。

A O(1)B O(n)C O(n 2)D O(log 2n) 8．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为【 】。

A 1140 B 1145 C 1120 D 1125 9．链表不具有的特点是【 】。

一、单项选择题（每小题3分，共30分）1、线性结构是数据元素之间存在的一种_______。

A、一对多关系B、多对多关系C、多对一关系D、一对一关系2、以下数据结构中，哪一个不是线性结构（）A．生成树 B. 顺序栈 C. 单链表 D. 循环队列3、设n是偶数，则运行下列程序段的时间复杂度为（）。

x=100;for(p=2;p<=n;p++)for(q=2*i;q<=n;q++)x=(x+1)*3;A．O(1) B.O(n) C.O(n2) D.O(lbn)4、若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。

A、散列B、顺序C、链式D、索引5、在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次为：p->llink=Q；p->rlink=q->rlink;q->rlink=p；_______.(空白处为一条赋值语句) A、q->llink=p B、q->rlink->llink=pC、p->rlink->llink=pD、p->llink->llink=p6、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A 、Q.front= = Q.rear; B、 Q.front - Q.rear= = Maxsize;C、Q.front + Q.rear= = Maxsize;D、 Q.front= = (Q.rear+1)% Maxsize;7、已知L是一个不带表头的单链表, 在表首插入结点*p的操作是（）。

A. p = L; p->next = L;B. p->next = L; p = L;C. p->next = L; L = p;D. L = p; p->next= L;8、下面关于串的叙述中，哪一个是不正确的？( )A．串是字符的有限序列 B.空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储9、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。

一、单项选择题(本题总分 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 ）。

《数据结构》期中考试试卷(供2012级计算机专业用)一、单项选择题，在括号内填写所选择的标号（每小题1分，共20分）1、算法指的是（）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2、如下陈述中正确的是（）A．串是一种元素仅为字符的线性表 B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串3、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A. O(1)B. O(n2)C. O(n)D. O(n/2)4、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A. n-2B. n-1C. nD. n+15．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear 分别为队列的队头指针和队尾指针) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。

A．QU->rear==(QU->front+1) % m0B．QU->rear==(QU->rear+1) % m0C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1)7．设有S1=“ABCDEFG”，S2=“PQRST”，函数con(x，y)返回x和y串的连接串，subs(s,i，j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个元素结点。

《数据结构》期中试卷专业________ 学号_________ 姓名________ 成绩_______一、选择题（本大题共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. 在数据结构中，从逻辑上可以把数据结构分成（）。

福建师范大学数学与计算机科学学院
2009--2010学年度上学期08电信
《数据结构》期中试题
试卷类别：闭卷考试时间：90分钟
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。

周遭流岚升腾，没露出那真实的面孔。

面对那流转的薄雾，我会幻想，那里有一个世外桃源。

在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。

偶尔，一片飞舞的落叶，会飘到我的窗前。

斑驳的印迹里，携刻着深秋的颜色。

在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。

窗外，是未被污染的银白色世界。

我会去迎接，这人间的圣洁。

在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。

《数据结构》期中考试试卷(供2012级计算机专业用)一、单项选择题，在括号内填写所选择的标号（每小题1分，共20分）1、算法指的是（）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2、如下陈述中正确的是（）A．串是一种元素仅为字符的线性表 B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串3、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A. O(1)B. O(n2)C. O(n)D. O(n/2)4、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A. n-2B. n-1C. nD. n+15．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear 分别为队列的队头指针和队尾指针) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。

A．QU->rear==(QU->front+1) % m0B．QU->rear==(QU->rear+1) % m0C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1)7．设有S1=“ABCDEFG”，S2=“PQRST”，函数con(x，y)返回x和y串的连接串，subs(s,i，j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个元素结点。

《数据结构》期中考试试卷(供2012级计算机专业用)一、单项选择题，在括号内填写所选择的标号（每小题1分，共20分）1、算法指的是（）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2、如下陈述中正确的是（）A．串是一种元素仅为字符的线性表 B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串3、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A. O(1)B. O(n2)C. O(n)D. O(n/2)4、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。

A. n-2B. n-1C. nD. n+15．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear 分别为队列的队头指针和队尾指针) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。

A．QU->rear==(QU->front+1) % m0B．QU->rear==(QU->rear+1) % m0C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1)7．设有S1=“ABCDEFG”，S2=“PQRST”，函数con(x，y)返回x和y串的连接串，subs(s,i，j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。

A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个元素结点。

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

满分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。

一、选择题（每小题 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）个。

厦门大学《＿数据结构＿》课程期中试卷信息科学与技术学院计算机科学系＿＿年级＿＿＿专业主考教师：＿＿＿＿试卷类型：（A卷/B卷）任选5题（（1，2），（3，4），（5，6），（7，8）中必须至少做一题），每题20分。

一、试设计一个双栈结构，它有两个端点end1和end2，满足从end1端插入的表目只能从end1端被删除，从end2端插入的表目只能从end2端被删除，并给出指定端i（i=1，2）的进栈push(S,e,i)和出栈pop(S,e,i)操作的算法描述。

再设计一个算法，它能够将一个有限长度的数据序列a1，a2，…，an，按照下标奇偶序号交替的方式将ai (1≤i≤n)分别从两端入栈，然后将数据出栈以实现整个数据序列的倒排。

该双栈宜采用顺序存储、栈顶迎面增长的存储方式，其形式定义如下：#define STACK_SIZE 1000typedef struct {SElemType base[STACK_SIZE];SElemType *top[3]; //top[1]表示end1端的栈顶指针，top[2]表示end2端的栈顶指针//初始值分别为base和base+STACK_SIZE-1}DSqStack;指定端i（i=1，2）的进栈push(S,e,i)和出栈pop(S,e,i)操作的算法描述如下：Status push(DSqStack &S, SElemType e, int i) {if ( S.top[1]-S.top[2]==1 ) //栈满exit(OVERFLOW);else if (i==1)*S.top[1]++ = e;else if (i==2)*S.top[2]-- = e;elsereturn ERROR;return OK;}Status pop(DSqStack &S, SElemType &e, int i) {if (i==1) {if ( S.top[1] == S.base ) return ERROR;e = *--S.top[1] = e;return OK;}else if (i==2) {if (S.top[2] == S.base+STACK_SIZE-1) return ERROR;e = *++S.top[2];return OK;} elsereturn ERROR;}基于上述结构的数据序列的倒排算法描述如下：Status resevers(DSqStack &S, SElemType a[], int n) {for (j=1;j<=n;j++)if (j%2==0) push(S, a[j-1],2);else push(S, a[j-1],1);for (j--;j>=1;j--)if (j%2==0) pop(S, a[n-j],2);else pop(S, a[n-j],1);return OK;}二、利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算。

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)))；后的输出结果是( )。

数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表是按照什么顺序排列的元素集合？A. 任意顺序B. 无序C. 有序D. 线性2. 链表与数组相比，其主要优点是什么？A. 节省空间B. 访问速度快C. 插入和删除操作灵活D. 内存分配简单3. 栈（Stack）是一种遵循什么原则的数据结构？A. 先进先出B. 先进后出C. 后进先出D. 后进后出4. 哈希表解决冲突最常用的方法是？A. 链接法B. 替换法C. 线性探测法D. 二次探测法5. 树和二叉树的主要区别是什么？A. 树的节点数可以比二叉树多B. 树的节点可以有多个子节点C. 树的节点可以没有子节点D. 树的节点可以有左子节点和右子节点6. 什么是二叉搜索树（BST）？A. 所有左子节点的值小于根节点的值B. 所有右子节点的值大于根节点的值C. 所有左子节点的值大于根节点的值D. A和B都正确7. 图的邻接矩阵表示法适用于哪种类型的图？A. 稠密图B. 稀疏图C. 有向图D. 无向图8. 排序算法的时间复杂度为O(n^2)的算法有哪些？A. 选择排序B. 冒泡排序C. 插入排序D. 所有以上9. 什么是递归？A. 函数调用自身B. 函数调用其他函数C. 循环结构D. 条件语句10. 动态规划主要用于解决什么问题？A. 排序问题B. 查找问题C. 优化问题D. 数据存储问题二、简答题（每题5分，共20分）1. 请简述链表和数组的区别。

2. 解释什么是图的深度优先搜索（DFS）。

3. 什么是二叉堆？请简述其性质。

4. 描述快速排序算法的基本思想。

三、编程题（每题15分，共30分）1. 编写一个函数，实现单链表的反转。

2. 编写一个函数，实现二叉树的前序遍历。

四、算法设计题（每题15分，共30分）1. 设计一个算法，用于在无序数组中找到第k小的元素。

2. 设计一个算法，实现最小生成树的克鲁斯卡尔算法。

五、综合应用题（10分）假设你正在开发一个在线图书管理系统，请设计一个数据结构来存储书籍信息，并实现以下功能：- 添加新书- 删除书籍- 查找特定书籍- 列出所有书籍请提供数据结构的设计思路和相应的伪代码。