2011 09级算法与数据结构 B卷

一、单项选择题（每小题2分，共30分）1.下列关于栈的叙述中，正确的是（）。

A．栈底元素一定是最后入栈的元素B．栈操作遵循先进后出的原则C．栈顶元素一定是最先入栈的元素D．以上三种说法都不对2.在数据结构中，与所使用的计算机硬件无关的是数据的（）结构。

A．逻辑B．存储C．逻辑和存储D．物理3.以下说法正确的是（）。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构4.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）A．546132 B．453126 C．346512 D．2341565.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（）A．8 B．9 C．10 D．116.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）7.下列陈述中正确的是（）A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，并且有左右之分8.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A．e B．2e C．n2－e D．n2－2e9.栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构10.在具有n个叶子结点的严格二叉树（即结点的度要么是0要么是2）中，结点总数为（）A．2n+1 B．2n C．2n-1 D．2n-211.在循环双链表的p所指的结点之前插入s所指结点的操作是（）。

数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（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)。

二1A三判断题（10分）（评分标准:2 V 3X 4 V 5X 6X 7 V选择题（202A 3A 4C 5B填空题（20分）（评分标准:6C 7C 8C（评分标准:每小题1分）8 V 9X 10X每小题2分）9C 10B每空1分）《数据结构与算法》试卷B答案及评分标准1.线性，非线性2.』3・链接（或链式）4.表屮一半,表长度和该元素衣表屮的位置5. nd 6.移动栈顶指针，存入元素7. 5 &遍历左了树,遍历右了树,访问根结点9. 0, n（n・l）/2 l（k 11.关键字相同的记录12. 3_ 13.插入,选择四、简答题（20分）（评分标准：每小题4分）1 •答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存屮可用存储单元的地址必须是连续的。

优点：存储密度大（ = 1?）,存储空间利用率高。

缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。

缺点：存储密度小（V1）,存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

若线性表的长度变化不大，且其主要操作是杳找，则采用顺序表；若线性表的长度变化较大，且-其主要操作是插入、删除操作, 则采用链表。

2•答：首元结点是指链表中存储线性表屮第一个数据元素迈的结点。

为了操作方便，通常在链表的首元结点Z 前附设一个结点，称为头结点，该结点的数据域屮不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。

头指针是指向链表屮第一个结点（或为头结点或为首元结点）的指针。

若链表屮附设头结点，则不管线性表是否为空表，头指针均不为空。

否则表示空表的链表的头指针为空。

这三个概念对单链表、双向链表和循环链表均适用。

是否设置头结点, 是不同的存储结构表示同一-逻辑结构的问题。

浙江科技学院考试试卷浙江科技学院2010 -2011 学年第 2 学期考试试卷 B 卷考试科目 数据结构 考试方式 闭 卷 完成时限 120分钟 拟题人 审核人 批准人 年 月 日 理学 院 09 年级 信息与计算科学 专业一、是非题（每小题1分，共10分）正确的在括号内打√，错误的打×.（ ）1. 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理.（ ）2. 数据结构是相互之间存在一种或多种关系的数据元素的集合，数据元素相互之间的关系称为结构.（ ）3. 对于抽象数据类型而言，不论其内部结构变化如何，只要它的数学特性不变，都不影响其外部的使用.（ ）4. 线性表的逻辑顺序与物理顺序总是一致的.（ ）5. 每种数据结构都应具备三种基本运算：插入、删除、搜索. （ ）6. 空串与由空格组成的串没有区别. （ ）7. 完全二叉树就是满二叉树.（ ）8. 已知一棵二叉树的前序序列和中序序列，则可以唯一地构造出该二叉树. （ ）9. 带权连通图的最小生成树的权值之和一定小于它的其他生成树的权值之和. （ ）10. 内部排序要求数据一定要以顺序方式存储.二、选择题（单项选择，每小题2分，共40分） 请将你认为正确的选项填入下表中。

专业班级 学号 姓名………………………………………………………………………装订线……………………………………………………………………………………1. 算法在发生非法操作时可以作出处理的特性称为（）.A. 正确性B. 易读性Ｃ.高效率 D. 健壮性2. 执行下面程序段时，执行S语句的次数为（）.for (int i = 1; i <= n; i ++)for (int j = 1; j <= i; j ++) S;A. 2nB. n/2C. n(n+1)D. n(n+1)/23. 数据结构的定义为（D, S），其中S是（）的集合.A. 算法B. 数据元素C. 关系D. 逻辑结构4. 有六个元素按照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 65. 广义表A（a），则表尾为（）.A. aB. （（））C. 空表D. （a）6. 二叉树中第4层上的结点最多为（）.A. 8B. 15C.16D. 327. 对右图所示二叉树，进行后序遍历的结果是（）.A. ABCDEFB. DBEAFCC. ABDECFD. DEBFCA8. 假设以行序为主序存储二维数组A = array[1..100,1..100]设每个数据元素占两个存储单元，基地址为10，则Loc[5,5]（）.A. 808B. 818C. 1010D. 10209. 具有35个结点的完全二叉树的深度为（）.A. 5B. 6C. 7D. 810. 若一棵二叉树具有9个度为2的结点，则该二叉树的度为0的结点个数是（）.A. 9B. 10C. 11D. 不确定11. 在有n个结点的二叉树的二叉链表表示中，空指针数为（）.A. 不定B. n+1C. nD. n-112. 具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）.A. n-1B. nC. n+1D. 2n13. 在完全二叉树中，若一个结点是叶子结点，则它没有（）.A. 左孩子结点B. 右孩子结点C. 左孩子结点和右孩子结点D. 左孩子结点，右孩子结点和兄弟结点14. 有m个叶子结点的哈夫曼树，其结点总数是（）.A. 2m-1B. 2mC. 2m+1D. 2（m+1）15. 任何一个无向连通图的最小生成树（）.A. 只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在16. 下列查找方法中，（）适合用于查找有序单链表.A. 顺序查找B. 二分查找C. 分块查找D. 哈希查找17. 在长度为100的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）.A. 99B.100C. 101D. 018. 对关键码序列28，16，32，12，60，2，5，72快速排序，若选28为枢轴记录关键字，则从小到大一次划分结果为（）.A. （2，5，12，16）28（60，32，72）B. （5，16，2，12）28（60，32，72）C. （2，16，12，5）28（60，32，72）D. （5，16，2，12）28（32，60，72）19. 下列排序算法中，（）排序在一趟结束后不一定能选出一个元素放在其最终位置上.A. 选择B. 冒泡C. 归并D. 堆20. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用的排序方法是（）.A. 快速排序B. 堆排序C. 插入排序D. 二路归并排序三、填空题（每空1分，共15分）1. 在线性结构中，____________具有先进先出特性，___________具有先进后出特性.2. 有向图的存储结构有______________、_____________、_____________等方法.3. 具有10个顶点的连通图的深度优先生成树，其边数为_________________.4. 已知U = ’xyxyxyxxyxy’，t = ’xxy’，StrAssign(S, U)，StrAssign(V, Substring(S, Index(s,t), StrLength(t)+1))，StrAssign(m,’ww’)求Replace(S, V, m)=___________________.5. 具有相同函数值的关键字对于哈希函数来说称作__________________.6. 已知一组待排序列的记录关键字初始排序为：56，34，58，26，79，52，64，37，28，84，57.若选中第一个记录关键字为枢轴记录，则一趟快速排序的结果为：_____________________；若建立大根堆，则初始堆为____________________.7. 由A, B, C, D, E五个结点构成的二叉树，共有_________种互不相似的结构.8. 长度为225的表，采用分块查找法，每块的最佳长度是______，应分为______块，若每块的长度为10，则平均查找长度为_________________.9. 快速排序在平均情况下的时间复杂度为_____________.四、应用题(共30分)1. （8分）已知一棵二叉树的中序序列和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的的结点个数.中序序列：CBDEAGIHJF；后序序列：CEDBIJHGFA2. （7分）假设用于通信的电文仅由8种字符母{A，B，C，D，E，F，G，H}组成，它们在电文中出现的频率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}。

湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷B专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）1、空串和空格串是相同的。

( )2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。

( )3、大顶堆（最大堆）中，最大值一定为根结点。

( )4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。

( )5、稀疏矩阵一般采用三元组顺序表方法压缩存储。

( )6、 若二叉排序树（搜索树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。

( )7、有向图用邻接表表示后，顶点i 的出度等于邻接表中顶点i 后链表的长度。

( ) 8、链接线性表是顺序存取的线性表。

( )9、哈希函数进行模除取余时，最好取素数进行模除。

（ ） 10、归并排序是一种稳定的排序算法。

（ ）二、填空题（本题共10小题，每小题 2 分，共计 20分）。

（请将正确答案填入空格内，答案是确定和唯一的）1、在数据结构中，从逻辑上可以把数据结构分成 和 。

2、限在表尾进行插入和删除操作的线性表称为 。

3、实现二分查找（对半搜索）的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的。

4、在拓扑排序中，拓扑序列的第一个顶点必须是 的顶点。

5、在一个长度为n 的顺序表中删除第i 个元素，则需要移动 个元素。

6、二维数组A[6，7]，按列优先存储，每个元素占4个字节,A 基址为500,则元素A[4,6]的存储地址是 。

7、深度为k二叉树中最多可有个结点。

8、任意写出二叉树的两种存储结构，分别是和。

9、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是。

10、快速排序平均时间复杂性为，平均空间复杂性。

三、选择题（本题共18小题，每小题 1分，共计 18 分）。

（从下列答案中选出一个正确答案，并将对应的字母填入括号内）1．线性表的顺序存储结构是一种( )的存储结构。

安徽大学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）。

西华大学课程考试参考答案（B卷）课程代码： 8401801 试卷总分： 100 分一、单项选择题参考答案及评分标准：（本大题共20个小题，每小题2分，共40分）评分标准：选对一题得2分，不选或选错得0分。

1-5：ABDBB 6-10：CABDC 11-15：BABCB 16-20：CABCC二、算法理解题参考答案及评分标准：（本大题共3个小题，第1、2小题各7分，第3小题6分，共20分）评分标准：请根据各解答步骤酌情给分。

1. 解答：构造过程各图（略），最后结果为：2. 解：设权w=(5,10,15,30,40)，可构造一棵赫夫曼树如下图所示。

所得赫夫曼编码为：A: 1110B: 1111C: 110D: 10E: 03. 解：（1）希尔排序第一趟（增量d=5）排序后 170、087、275、061、426、503、897、512、653、908第二趟（增量d=3）排序后 061、087、275、170、426、503、897、512、653、908第三趟（增量d=1）排序后 061、087、170、275、426、503、512、653、897、908（2）基数排序第一趟排序后 170、061、512、503、653、275、426、087、897、908第一趟排序后 503、908、512、426、653、061、170、275、087、897第三趟排序后 061、087、170、275、426、503、512、653、897、908三、算法设计题参考答案及评分标准：（本大题共4个小题，每小题10分，共40分）评分标准：请根据编程情况酌情给分。

1. 参考答案示例：LinkList Delete(LinkList L）∥L是带头结点的单链表，本算法删除其最小值结点。

p=L->next；∥p是链表的工作指针pre=L；∥pre指向链表中数据域最小值结点的前驱。

q=p；∥q指向数据域最小值结点，初始假定是首元结点while （p->next!=NULL）{ if（p->next->data<q->data）{ pre=p；q=p->next；} ∥找到新的最小值结点p=p->next；}pre->next=q->next；∥将最小值结点从链表上去掉free（q）；∥释放最小值结点空间}∥Delete2. 参考答案示例：int BTreeEqual(BiTNode * T1, BiTNode * T2){//判断两棵二叉树是否相等，若相等则返回1否则返回0。

四川大学期末考试试题（闭卷）（2009~2010学年第2学期）课程号： 311036030 课程名称：数据结构与算法（B卷）任课教师：孙界平杨秋辉张卫华适用专业年级：软件工程 2009级学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。

有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。

四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。

有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。

题号一(30%) 二(10%) 三(15%) 四(20%) 五(25%) 卷面成绩得分阅卷时间注意事项：1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；2. 请将答案全部填写在本试题纸上；3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。

一、单项选择题（本大题共15小题，每小题2分，共30分）提示：在每小题列评阅教师得分出的四个备选项中只有一个是符合题目要求的，请将其代码填写在答题纸上。

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

1. A mathematical function is most like a ( A )(A) Problem(B) Algorithm(C) Program(D) Code2. A recurrence relation is often used to model programs with ( C )(A) for loops.(B) branch control like "if" statements.(C) recursive calls.(D) function calls.3. For an air traffic control system, the most important metric is: ( C )(A) The best-case upper bound.(B) The average-case upper bound.(C) The worst-case upper bound.(D) The best-case lower bound.4. For a list of length n, the linked-list implementation's prev() function requires worst-case time: ( C )(A) O(1).(B) O(log n).(C) O(n).(D) O(n2).5. Assume a BST is implemented so that all nodes in the left subtree of a given node have values less than that node, and all nodes in the right subtree have values greater than or equal to that node. When implementing the delete routine, we must select as its replacement: ( B )(A) The greatest value from the left subtree.(B) The least value from the right subtree.(C) Either of the above.(D) The root.6. The primary ADT access functions used to traverse a general tree are: ( C )(A) left child and right sibling(B) left child and right child(C) leftmost child and right sibling(D) leftmost child and next child7. A sorting algorithm is stable if it: ( B )(A) Works for all inputs.(B) Does not change the relative ordering of records with identical key values.(C) Always sorts in the same amount of time (within a constant factor) for a given input size.(D) Most efficient.8. When sorting n records, Quicksort has worst-case cost: ( D )(A) O(log n).(B) O(n).(C) O(n log n).(D) O(n2)9. The basic unit of I/O when accessing a disk drive is: ( B )(A) A byte.(B) A sector.(C) A cluster.(D) A track.10. The sorting algorithm used as a model for most external sorting algorithms is: ( C )(A) Insertion sort.(B) Quicksort.(C) Mergesort.(D) Radix Sort.11. Which of the following is often implemented using a self-organizing list? ( A )(A) Buffer pool.(B) Linked list.(C) Priority queue.(D) B-Tree12. An entry-sequenced file stores records sorted by: ( C )(A) Primary key value.(B) Secondary key value.(C) Order of arrival.(D) Frequency of access.13. The primary difference between a B-tree and a B+-tree is: ( A )(A) The B+-tree store records only at the leaf nodes.(B) The B+-tree has a higher branching factor.(C) The B+-tree is hight balanced.(D) The B+-tree is smaller.14. The goal of a topological sort is to: ( B )(A) Sort all of the graph vertices by value.(B) Sort all of the graph vertices so that each vertex is listed prior to any others that depend onit.(C) Sort all of the graph vertices by distance from the source vertex.(D) None of the above.15. Which is a good example of a greedy algorithm? ( B )(A) Floyd's all-pairs shortest path algorithm.(B) Prim's minimal-cost spanning tree algorithm.(C) Depth-first search.(D) T opological sorting.二、判断题（本大题共5小题，每小题2分，共10分）提示：正确打T，错误打F，评阅教师得分将其结果填写在答题纸上。

装订线合肥学院2009至2010学年第2学期算法与数据结构课程考试(B )卷数学与物理系08级信息与计算科学专业学号姓名一、单选题(共20分。

每小题2分。

)01、算法分析的主要任务是分析__ __。

A)算法是否具有较好的可读性B)算法中是否存在语法错误C)算法的功能是否符合设计要求D)算法的执行时间和问题规模之间的关系02、在一个带头结点的双向循环链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->next赋值为__ __。

A)p->priorB)p->nextC)p->next->next D)p->prior->prior03、判定栈S(元素个数最多n个)满的条件是__ __。

A)S->top==0 B)S->top!=0C)S->top!=n-1 D)S->top==n-104、设矩阵A是一个对称矩阵(下标从1开始)，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，则下三角部分中任一元素ai,j(i≤j), 在一维数组B 中下标k的值是_ _。

A) i*(i-1)/2+j-1 B)i*(i-1)/2+jC) i*(i+1)/2+j-1 D)i*(i+1)/2+j05、如果二叉树中结点的前序序列是...a...b...，中序序列是...b...a...，则__ __。

A)结点a和结点b分别在某结点的左子树和右子树中B)结点b在结点a的右子树中C)结点b在结点a的左子树中D)结点a和结点b分别在某结点的两棵非空子树中06、有n个叶子的哈夫曼树的结点总数为_ _。

A)不确定 B)2n C)2n+1 D)2n-107、下图若从顶点a出发按深度优先搜索法进行遍历，则得到的顶点序列是__ __。

A)abecd B)acebd C)aebcd D)aedcb08、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。