北京理工大学2013级数据结构B试题(A卷)-答案
一、选择题
1、从逻辑结构上可以把数据结构分为【C 】。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。
A、n-i
B、n-i+1
C、n-i-1
D、i
3、链表结构不具有下列【B 】特点。
A、插入和删除无需移动元素
B、可随机访问链表中的任意元素
C、无需实现分配存储空间
D、所需空间与结点个数成正比。
4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行【 C 】。
A、s->next = p->next; p->next = s;
B、p->next = s->next; s->next = p;
C、q->next = s; s->next = p;
D、p->next = s; s->next = q;
5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【C 】。
A、54321
B、45321
C、43512
D、12345
6、判断一个队列Q（元素最多为M个）为空的条件是【C 】。
A、Q->rear – Q->front = M
B、Q->rear – Q->front -1 ==M
C、Q->rear == Q->front
D、Q->rear + 1 == Q->front
7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【A 】。
A、r->next = s; r=s;
B、f->next = s; f=s;
C、s->next = r; r=s;
D、s->next = f; f=s;
8、深度为5的二叉树至多有【A 】个结点。
A、31
B、32
C、16
D、10
9、在一非空二叉树的中序遍历序列中，根结点的右边【A 】。
A、只有右子树上的所有结点
B、只有右子树上的部分结点
C、只有左子树上的所有结点B、只有左子树上的部分结点
10、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【D 】。
A、250
B、500
C、502
D、490
11、在一个图中，所有顶点的度数之和是所有边数的【C 】倍。
A、1/2
B、1
C、2
D、4
12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的【A 】。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
13、一个有n个顶点的无向图最多有【D 】条边。
A、n
B、n(n-1)
C、2n
D、n(n-1)/2
14、静态查找表与动态查找表的根本区别在于【B 】。
A、它们的逻辑结构不同
B、施加在其上的操作不同
C、所包含的数据元素类型不同
D、存储实现不一样
15、顺序查找适用于存储结构为【C 】的线性表。
A、哈希存储
B、压缩存储
C、顺序存储或链式存储
D、索引存储
16、若一颗二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足【B 】。
A、所有结点均无孩子
B、所有结点均无右孩子
C、只有一个叶子结点
D、是一颗满二叉树
17、二叉排序树是【B 】。
A、每一分支结点的度均为2的二叉树
B、中序遍历得到一升序序列的二叉树
C、按从左到右顺序编号的二叉树
D、每一分支结点的值均小于左子树上所有结点的值，又大于右子树上所有结点的值
18、具有12个记录的序列，采用冒泡排序最少的比较次数是【C 】。
A、1
B、144
C、11
D、66
19、堆的形状是一棵【C 】。
A、二叉排序树
B、满二叉树
C、完全二叉树
D、平衡二叉树
20、在一个包含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为【D 】。
A、e
B、2e
C、n2-e
D、n2-2e
二、判断对错
【x 】1、具有n个顶点的连通图至少有n条边。
【x 】2、链表的单个结点内部的存储空间可以是不连续的。
【√】3、栈和队列的共同点是只允许在端点处插入和删除元素。
【√】4、使用循环队列可以解决队列顺序存储时的假溢出问题。
【x 】5、要想通过遍历序列还原为惟一二叉树，应当知道其先序序列和后序序列。
【√】6、若一个结点是某二叉树子树的中序遍历序列的第一个结点，则它也必是该子树的后序遍历序列的第一个结点。
【x 】7、完全二叉树可采用顺序存储结构存储，非完全二叉树则不能。
【√】8、对于一棵含有n个结点的完全二叉树，将其结点按从上到下且从左至右按1至n进行编号，则对其任意一个编号为i的结点，如果它有左孩子，则其左孩子结点的编号为2i。
【√】9、哈夫曼树的所有子树也都是哈夫曼树。
【x 】10、当图的边较少而结点较多时，求其最小生成树用Prim算法比用Kruskal 算法效率更高。
三、填空题
1、向量的第一个元素的存储地址是200，每个元素的长度是3，那么第6个元素的存储地址是。
答案：215
2、在一个带头结点的单链表中，p所指结点既不是首元结点，也不是尾元结点，删除p 结点的语句序列是、、。
答案: q=p，p=p->next，free(q)
3、设堆栈有足够的存储空间，那么向堆栈中插入一个数据元素，即入栈的操作过程是、。
答案: 存入数据元素，栈顶指针加1
4、一般情况下，向循环队列中插入数据元素时，需要判满队列是否已经满了，判断条件是：。
答案: (rear+1)%MaxSize == front
6、已知循环队列用数组data[1…n]存储元素值，front和rear分别表示队头和队尾指针，则当前队列中元素的个数为。
答案: (n+rear-frone)%n或(n+rear-frone) mod n
7、深度为k的二叉树最多有个结点，深度为k的完全二叉树最少有个结点（k≥1）。答案: 2k-1，2k-1
8、如以{2,3,6,7,9}作为叶子结点的权值构造哈夫曼树，则其最短带权路径长度为。
答案: 55
10、已知某二叉树的中序序列和前序序列分别为42758136、12457836，则它的后序序列为。
答案: 47852631
12、在有n个顶点的有向图中，每个顶点的度最大可达到。
答案: 2(n-1)
13、在有序表A[1…18]中，采用折半查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为。
答案: 9 4 6 7
14、一组记录的输入顺序为(25,38,65,90,72,14)，则利用堆排序方法建立的初始“小顶堆”为。
答案: 14,38,25,90,72,65
四、简答题
1、设有一段正文是由字符集{a, b, c, d, e, f, g, h}组成，正文长度为100个字符，其中
每个字符在正文中出现的次数分别为17, 12, 14, 4, 10, 9, 20, 3。若采用哈夫曼树对这
段文字进行压缩存储，请完成如下工作：
（1）构造哈夫曼树（规定权值较小的结点为左子树）；
（2）求出每个字符的哈夫曼编码；
（3）若其中一段正文的二进制编码序列为“10111100011000101”，请按（2）的哈夫曼编码将其译码成原始正文。
答案：
（1）树的结构为：
（2）编码为a=111，b=101，c=110，d=0001，e=100，f=001，g=01，h=0000 （3）
上述编码序列的对应原文为：badegg
2、一棵有11个结点的二叉树的存储情况如下图所示（其中“∧”表示空指针），left[i]和right[i]分别表示结点i的左、右孩子，根结点是序号为3的结点，要求：（1）画出该二叉树；
（2）分别写出该二叉树的前序和中序遍历序列。
第2题图
答案：
（1）二叉树的结构如图所示：
（2）前序序列ALKRSECFMBD
中序序列RKSLEAFCBDM
3、设数据集合D={2, 24, 12, 15, 32, 9, 10, 35, 7, 5}，要求：
（1）依次读取D中的各个数据，构造一棵二叉排序树Bt；
（2）如何根据此二叉树Bt求得数据集合D的一个有序序列？并写出该有序序列；（3）画出在上述二叉树中删除结点“12”后得到的二叉树结构。
答案：
（1）构造的二叉排序树如下：
一、单项选择题 1．算法必须具备的三个特性是( )。 A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 2．下列数据中，( )是非线性数据结构。 A．栈B．队列 C．完全二叉树D．顺序表 3．算法分析的两个方面是( )。 A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 4．非空的循环单链表head的尾结点p满足( )。 A．p->next==head B．p->next==NULL C．p==NULL D．p==head 5．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( )。 A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 6．按照二叉树的定义，具有3个结点的二叉树有( )种。 A．3 B．4 C．5 D．6 7．在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的( )倍。 A．1/2 B．1 C．2 D．4 8．二叉排序树是( )。 A．每一分支结点的度均为2的二叉树 B．中序遍历得到一升序序列的二叉树 C．按从左到右顺序编号的二叉树 D．每一分支结点的值均小于左子树上所有结点的值，大于右子树上所有结点的值9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( )。 A．1和 5 B．2和4 C．4和2 D．5和1 10．下列说法中正确的是( )。 A．堆栈是在两端操作、先进后出的线性表 B．堆栈是在一端操作、先进先出的线性表 C．队列是在一端操作、先进先出的线性表 D．队列是在两端操作、先进先出的线性表
课程编号：03000138 北京理工大学2013～2014学年第一学期 2011级机械设计基础期末试题A卷答案班级学号姓名成绩 一、是非题（正确的在括号内划√，错误的划×，每题2分，共10分） 1. 滚动轴承座圈和滚动体的常用材料是45钢调质。(F) 2. 在铰链四杆机构中，压力角越小，机构的传动性能越好。（T） 3. 带传动中对带的疲劳寿命影响最大的应力是小带轮上的弯曲应力（T） 4. 只要是渐开线标准齿轮，在齿轮齿廓上任一位置处的压力角都应为国家标准值20o（F） 5. 滚动轴承为标准件，为便于互换和生产，轴承内圈孔与轴的配合应采用基轴制（F） 二、选择题（把正确的答案选项填入空格内，每题2分，共20分） 1. 利用范成法加工渐开线标准齿轮时，若被加工的齿轮（D ）太小，就会发生根切现象。 A 模数 B 压力角 C 齿厚 D 齿数 2. 设计凸轮时，若工作行程中的最大压力角大于许用压力角，则应（A）。 A 增大基圆半径 B 减小基圆半径 C 增大滚子半径 D 减小滚子半径 3. 只承受弯矩而不传递转矩的轴称为（C ）。 A 传动轴 B 转轴 C 心轴 D 曲轴 4. 为了提高齿轮的齿面接触疲劳强度，可以（B ）。 A 加大模数 B 加大中心矩 C 减小齿宽系数 D 减小啮合角 5. 键的长度主要是根据( B )来选择。 A传递转矩大小 B 轮毂长度 C 轴直径 D 键剖面尺寸 6. 被连接件受横向外力作用时，如采用普通螺栓连接，则螺栓可能的失效形式为（C ）。 A 剪切破坏B挤压破坏 C 拉、扭联合作用下断裂D 拉、扭联合作用下塑性变形 7. 在载荷不平稳且有较大冲击和振动的情况下，一般宜选用（C）联轴器。 A 刚性 B 无弹性元件挠性 C 有弹性元件挠性 D 安全 8. 在同样载荷和同样工作条件下运转的同一批生产的同型号的滚动轴承，它们的寿命一般（B）。 A 相同 B 不相同 C 90%轴承相同 D 10%轴承相同 9. 在轴的初步计算中，轴的直径是按（B）进行初步确定的。 A 弯曲强度 B 扭转强度 C 轴段长度 D 轴段上所装配零件的孔径。 10. 蜗杆传动热平衡计算的目的是为了控制温升，防止（B）。、 A 蜗杆力学性能下降 B 润滑油变质和胶合 C 传动效率下降 D 蜗轮材料退火 三、（本题8分）试计算图示机构的自由度，若含有复合铰链、局部自由度和虚约束请指出，并判断该机构是否具有确定的运动。
《数据结构》试题（A卷） （考试时间： 90分钟） 一、单项选择题（本大题共15小题，每小题2分，共30分） （每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分） 1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。 A．数据 B.数据元素 C.数据对象 D.数据结构 2.算法计算量的大小称为算法的（）。 A.效率????? B.复杂度 C.数据元素之间的关系??? ? D.数据的存储方法 3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（ ）方式最节省时间。 A.链式存储 B. 索引存储 C.顺序存储 D.散列存储 4.下述哪一条是顺序存储结构的优点？（） A.存储密度大? B.插入运算方便? C.删除运算方便? D.可方便地用于各种逻辑结构的存储表示 5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。 >next=p->next->next >next=p->next =p->next;p->next=p->next->next =p->next->next 6.带头结点的单链表head为空的判定条件是（）。 ==NULL >next==NULL >next==head !==NULL 7.非空的循环单链表head的尾结点(由p所指向)满足（）。 >head==NULL ==NULL >next==head ==head 8.下面关于线性表的叙述中，错误的是哪一个？（） A.线性表采用顺序存储，必须占用一片连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链式存储，不必占用一片连续的存储单元。 D.线性表采用链式存储，便于插入和删除操作。 9.队列操作的原则是（）。 A.后进先出 B.先进先出 C.只能进行插入 D.只能进行删除 10.栈中允许进行插入和删除的一端称为（）。 A.栈首 B.栈尾 C.栈顶 D.栈底 11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（）。 A．（rear-front+n）%n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n 12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（）。 A.（rear+1）%n==front ==front +1==front D.(rear-1)%n==front 13.将一个十进制的数转换成二进制的数，可以使用以下一种称为（）的数据结构。 A. 图 B. 树 C. 广义表 D. 栈 14. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A. 有2种 B. 有3种 C. 有4种 D. 唯一的 15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（）。 A. 3 B. 2 C. 0 D. 不确定
一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元 素时，需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点， 则执行【C】。 A、s->next = p->next; p->next = s; B、p->next = s->next; s->next = p; C、q->next = s; s->next = p; D、p->next = s; s->next = q; 5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。 A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M C、Q->rear == Q->front D、Q->rear + 1 == Q->front 7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。 A、r->next = s; r=s; B、f->next = s; f=s; C、s->next = r; r=s; D、s->next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点B、只有左子树上的部分结点 10、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【 D 】。 A、250 B、500 C、502 D、490 11、在一个图中，所有顶点的度数之和是所有边数的【 C 】倍。 A、1/2 B、1 C、2 D、4 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的【 A 】。
2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、下列说法不正确的是（）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、线性表的顺序存储结构是一种（）。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序 方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。 Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。 A.107 B.108 C.214 D.215 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 10、下面关于B和B+树的叙述中，不正确的是（） A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000二、3（20/8分）】 A．效率 B.复杂性 C.现实性 D.难度 2. 算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】 A．问题的规模 B.待处理数据的初态 C. A 和 B 3.计算机算法指的是（ 1），它必须具备（ 2）这三个特性。 (1) A．计算方法 B.排序方法 C.解决问题的步骤序 列 D.调度方法 (2) A ．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D.易读性、稳定性、安全 性 【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（）。【中山大学1998二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特 性D．A 和 C. 5. 下面关于算法说法错误的是（）【南京理工大学2000一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错 误的 6. 下面说法错误的是（）【南京理工大学2000一、 2（ 1.5分）】 (1 ）算法原地工作的含义是指不需要任何额外的辅助空间 （ 2）在相同的规模n 下，复杂度 O(n) 的算法在时间上总是优于复杂度 n O(2 ) 的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A． (1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（ 2 分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000二、 1（2分）】 A．循环队列 B.链表 C.哈希表 D.栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001一、 1（2分）】 A．广义表 B.二叉树 C.稀疏矩阵 D.串
《数据结构》试卷 选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分) 1.在数据结构中，与所使用的计算机无关的是数据的（）结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存 储方式节省时间。 A.单链表 B.双链表 C.顺序表 D.单循环链表 3.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。 A.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1 B.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 C.-1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 D.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1， 4.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个 元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 5.一棵含有101个结点的完全二叉树存储在数组bt[102]中，其中bt[0]不用，若bt[k] 是叶子结点，则k的最小值是（）。 A.51 B.50 C.49 D.48 6.稀疏矩阵一般的压缩存储方法有两种，即（）。 A.二维数组和三维数组 B.三元组表和散列表 C.三元组表和十字链表 D.散列表和十字链表 7.对顺序存储的18个数据元素（A[1]~A[18]）的有序表做二分查找，则查找A[3]的 比较序列的下标为( )。 A.1，2，3 B.9，5，2，3
C.9，5，3 D.9，4，2，3 8.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与 图中的结点的个数有关，而与图的边数无关，这种说法（）。 A.正确 B.错误 9.下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是（ ）。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序 10.在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已 知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型 调整使其平衡。 A.LL B.LR C.RL D.RR 11.在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机 将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该 缓冲区应是一个（）结构。 A.堆栈 B.队列 C.顺序表 D.链表 二、填空题（每空2分，共18分） 1.以下程序段的时间复杂度是________________________，其中n为正整数。 int i=1; while(i<=n) i=i*2; 2.对顺序存储结构的线性表，设表长为n；在等概率假设条件下，插入一个数据元素 需平均移动表中元素______________个；在最坏情况下需移动表中元素 ______________个。 3.设树T的度为4，其中度为1、2、3、4的结点的个数分别为4、3、2、1，则树T 的叶子结点的个数是。 4.判定一个环形队列qu（最多元素为MaxSize）为空的条件是 __________________________________________，判定环形队列qu为满队列的条
第 1 页/共 4 页 考试类别[学生填写]（□正考 □补考 □重修 □补修 □缓考 □其它） 1、以下属于逻辑结构的是（ ） A ）顺序表 B ）散列表 C ）有序表 D ）单链表 2、以下算法的时间复杂度为（ ） void fun(int n){ int i=1; while(i<=n) i=i*2; } A ）O(n) B ）O(n 2 ) C ）O(nlog 2 n) D ）O(log 2 n) 3、若线性表最常用的操作是存取第i 个元素及其前驱和后继元素的值，为了提高效率，应采用（ ）的存储方式。 A ）单链表 B ）双向链表 C ）单循环链表 D ）顺序表 4、设线性表中有2n 个元素，（ ）算法，在单链表上实现要比在顺序表上实现效率更高。 A ）删除所有值为x 的元素 B ）在最后一个元素的后面插入一个新元素 C ）顺序输出前k 个元素 D ）交换第i 个元素和第2n – i – 1个元素的值（i=0，…，n-1） 5、栈和队列的主要区别在于（ ） A ）它们的逻辑结构不一样 B ）它们的存储结构不一样 C ）所包含的元素不一样 D ）插入、删除操作的限定不一样 6、设有一个10阶的对称矩阵A[10][10], 采用压缩存储方式按行优先将矩阵中下三角部分的元素存入一维数组B 中，A[0][0]存入B[0]中，则A[8][5]在B 中的位置是( ) A ）32 B ）33 C ）41 D ）65 7、树最适合用来表示（ ）的数据。 A ）有序 B ）无序 C ）任意元素之间具有多种联系 D ）元素之间具有分支层次关系 8、高度为h 的完全二叉树最少有（ ）个结点。 A ）2h B ）2h +1 C ）2h-1 D ）2h -1 9、假设一个有n 个顶点和e 条边的有向图用邻接表表示，则删除与某个顶点v i 相关的所有边的时间复杂度为（ ） A ）O(n) B ）O(e) C ）O(n+e) D ）O(ne) 10、无向图G=(V, E)，其中V={a ，b ，c ，d ，e ，f}，E={（a ，b ），（a ，e ），（a ，c ），（b ，e ），（c ，f ），（f ，d ），（e ，d ）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ） A ）a ，b ，e ，c ，d ，f B ）a ，c ，f ，e ，b ，d C ）a ，e ，b ，c ，f ，d D ）a ，e ，d ，f ，c ，b 11、对于顺序存储的有序表（5, 12, 20, 26, 37, 42, 46, 50, 64），若采用折半查找，则查找元素26的查找长度为（ ） A ）2 B ）3 C ）4 D ）5 12、采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ） A ）数据元素过多 B ）装载因子过大 C ）散列函数选择不当 D ）解决冲突的方法选择不当 13、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ） A ）直接插入排序 B ）选择排序 C ）基数排序 D ）快速排序 14、对以下数据序列利用快速排序进行排序，速度最快的是（ ） A ）{21，25，5，17，9，23，30} B ）{25，23，30，17，21，5，9} C ）{21，9，17，30，25，23，5} D ）{5，9，17，21，23，25，30} 15、堆是一种有用的数据结构，下列排序码中序列中，（ ）不是一个堆。 A ）100，85，98，77，80，60，82，40，20，10，66 B ）100，98，85，82，80，77，66，60，40，20，10 C ）10，20，40，60，66，77，80，82，85，98，100 D ）100，85，40，77，80，60，66，98，82，10，20 二、填空题（每空2分，共10分） 下面是折半插入排序算法的实现，请补充完整代码。 void InsertSort(ElemType A[], int len) { int i, j, low, high, mid; for(i=2; i<=len; i++) { A[0]=A[i]; low=1; high=__________; while(__________________) { 线 订 装 郑州轻工业学院2013 — 2014学年 第 1 学期 数据结构 试卷 B 卷 专业年级及班级 姓名 学号
数据结构试题和答案 A卷 一、填空题（共8 小题，每空 1 分，共计20 分） 1．栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和在_队头_删除元素。 2．一个广义表中的元素分为单元素和表元素两类。 3．对于一个长度为n的顺序存储的线形表，在表头插入元素的时间复杂度为__ O(n)_______，在表尾插入元素的时间复杂度为____ O(1)_______。 5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于 n+1 。6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。 7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。 8．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（15，02，21，24，26，57，43，66，80，48，73）。 9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。 10.在线形表的散列存储中，处理冲突有开放定址法和链地址法两种方法。 11.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有______12______ 个叶子的结点。 12.设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是_ E,F,H ___。 13．若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 4 ,带权路径长度为 87 。 二、选择题（共15小题，每题 1 分，共计15 分） 1．算法指的是（ D ） A．计算机程序 B．解决问题的计算方法
课程编号：MTH17171 北京理工大学2014-2015学年第二学期 2013级最优化方法期末试题A 卷 一、（10分）设()f x 是凸集n S R ?上的凸函数，对12 ,x x S ∈，实数[]0,1α?， 令()121z x x ααα=+-，若z S α∈，证明()() ()121f z f x x ααα≥+-。 二、（10分）设数列{} k x 的通项为：221 21,2,0,1,! i i i x x x i i +===L ， 证明：（1）{} k x 收敛于* 0x =； （2）令1 ,0,1,k k k x x d k +=+=L ，则*lim 1k k k x x d →∞ -=； （3）{} k x 不是超线性收敛于* x 的。 三、（10分）求解整数规划问题： 12 12121212min ..14951631,0,,z x x s t x x x x x x x x =-++≤-+≤≥∈Z 。 （图解法，割平面法，分枝定界法均可） 四、（10分）设f 连续可微有下界，且f ?Lipschitz 连续，即：存在常数0L > ，使得 ,n x y R ?∈，()()f x f y L x y ?-?≤-，设{} k x 由Wolfe-Powell 型搜索产生，k d 为下 降方向，()()cos T k k k k k f x d f x d θ?=- ??， 证明：（1） () 2 20 cos k k k f x θ∞ =?<∞∑； （2）若0δ?>，使得k ?，cos k θδ≥，则() lim 0k k f x →∞ ?=。 五、（10分）设f 连续可微，序列{} k x 由最速下降法解()min f x ，并做精确搜索产生，证明：0,1,k ?=L ，( )()10T k k f x f x +??=。
数据结构试题及答案(十套)数据结构试题及答案(十套) 一、选择题 1. 数据结构是指（）。 A. 存储数据的方式 B. 数据的逻辑结构和物理结构 C. 数据的存储结构和存储方式 D. 数据的逻辑结构、存储结构和存储方式 答案：D 2. 在数据结构中，线性表的存储方式包括（）。 A. 顺序存储和链式存储 B. 数组存储和链表存储 C. 顺序存储、链表存储和索引存储 D. 顺序存储、链表存储和树形存储 答案：A 3. 栈是一种（）的数据结构。 A. 先进先出
B. 先进后出 C. 后进先出 D. 后进后出 答案：C 4. 队列是一种（）的数据结构。 A. 先进先出 B. 先进后出 C. 后进先出 D. 后进后出 答案：A 5. 二叉树中，度为0的节点称为（）。 A. 叶子节点 B. 根节点 C. 中间节点 D. 子节点 答案：A 6. 以下哪个排序算法是稳定的？
A. 快速排序 B. 选择排序 C. 插入排序 D. 希尔排序 答案：C 7. 图中表示顶点之间关系的边的数量称为（）。 A. 顶点度数 B. 边数 C. 路径数 D. 网络 答案：B 8. 哈希表通过（）来实现高效的查找操作。 A. 散列函数 B. 排序算法 C. 遍历操作 D. 顺序存储 答案：A
9. 平衡二叉树是一种具有左右子树高度差不超过（）的二叉树。 A. 0 B. 1 C. 2 D. 3 答案：B 10. 在链表中，删除节点的操作时间复杂度是（）。 A. O(1) B. O(logn) C. O(n) D. O(nlogn) 答案：A 二、填空题 1. 在顺序存储结构中，元素之间的逻辑关系由（）表示。 答案：下标 2. 二叉查找树的中序遍历结果是一个（）序列。 答案：递增 3. 哈希表通过散列函数将关键字映射到（）上。
西安电子科技大学 考试时间 120 分钟 试题（A） 题号一二三四五六七八九十总分 分数 1.考试形式：闭卷；2。考试日期：2013年月日3.本试卷共四大题，满分100分。 班级学号姓名任课教师 一、单选题（15小题，每题2分，共30分） 1. 以下关于数据结构的描述正确的是（B ） A．数据的逻辑结构描述了数据项与数据项之间存在的某种关系 B．数据结构操作的实现与存储结构有关 C．数据的逻辑结构相同，对应的存储结构也相同 D．数据结构的抽象数据类型中操作的定义与存储结构有关 2. 关于算法的时间复杂度的描述正确的是（C ） A．时间复杂度相同的算法在相同的计算机上的运行时间相同 B．时间复杂度相同的算法在解决问题的规模相同时运行时间相同 C．算法的时间复杂度仅反映算法的运行时间与问题规模之间的关系 D．算法的时间复杂度与问题的规模和计算机硬件的运行速度相关 3. 在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（B ） A．O(n) B．O(1) C．O(n2) D．O(log2n) 4. 已知单链表中结点*q是结点*p的直接前驱，若在*q与*p之间插入结点*s，需要执行的操作是（ A ） A．s->next= q->next; q->next=s; B．s->next=p->next; p->next=s; C．q->next=s; s->next= q->next; D．p->next=s; s->next=q; 5. 下列哪种操作利用到了栈的结构（A ） A．递归函数调用B．树的层次遍历 C．顺序查找D．选择排序 6．设有一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A中的元素A[i][j]存放于B中的存放位置是（A ） A．(i+1)*i/2+j B．(i+1)*j/2+j
程序复杂性 3、具有线性结构的数据结构是 D ; A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、B等5个特性; A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是C ; fori=0;i
北京理工大学智慧树知到“计算机科学与技术”《数据结 构与算法》网课测试题答案 （图片大小可自由调整） 第1卷 一.综合考核(共15题) 1.设有一个二维数A[m][n]，以行序为主序存储。假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)表明用10进数表示。 A.692(10) B.626(10) C.709(10) D.724(10) 2.对线性表进行二分查找时，要求线性表必须()。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 3.对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。 A.顺序存储结构 B.链式存储结构 C.线性链表 D.栈 4.用链接方式存储的队列，在进行插入运算时()。 A.仅修改头指针 B.头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改 5.下述几种排序方法中，平均查找长度最小的是()。 A.插入排序 B.选择排序 C.快速排序 D.归并排序 6.在线性表顺序存储结构下，在第i个元素之前插入新元素一般需要() A.移动元素 B.修改头指针 C.队头指针 D.申请新的结点空间 7.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。 A.1 B.2 C.4 D.8 8.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 9.任何一个无向连通图的最小生成树()。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 10.下列关于AOE网的叙述中，不正确的是()。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动提前完成，那么整个工程将会提前完成 11.栈与一般的线性表的区别在于()。 A.数据元素的类型不同 B.运算是否受限制 C.数据元素的个数不同 D.逻辑结构不同 12.下列排序方法中，排序趟数与序列的原始状态有关的方法是()。 A.选择排序 B.希尔排序 C.堆排序 D.冒泡排序 13.若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存
数据结构试卷A 一、单选题（每小题 2 分，共 8 分） 1、在一个长度为 n 的顺序线性表中顺序查找值为 x 的元素时，查找成功时的平均查找长度（即 x 与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( ) 。 A n B n/2 C (n+1)/2 D (n-1)/2 2、在一个单链表中 , 若 q 所指结点是 p 所指结点的前驱结点 , 若在 q 与 p 之间插入一个 s 所指的结点 , 则执行 ( ) 。 A s →next=p →next; p →next=s; B p →next=s; s →next=q; C p →next=s →next; s →next=p; D q →next=s; s →next =p; 3、栈的插入和删除操作在（）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） A 24 B 71 C 48 D 53 二、填空题（每空 1 分，共 30 分） 1、数据的逻辑结构被分为 __________ 、 ___________ 、 ________ 和 ________ 四种。 2、一种抽象数据类型包括 ______________ 和 _____________ 两个部分。
3、在下面的数组 a 中链接存储着一个线性表，表头指针为 a[0].next ，则该线性表为 _________________________________________________ 。 0 1 2 3 4 5 6 7 8 4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为 ________________ 和 ____________________ 。 5、用具有 n 个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的 ___________ ，该循环队列的最大长度为 __________ 。 6、当堆栈S采用顺序存储结构时，栈顶元素的值可用表示；当堆栈采用链接存储结构时，栈顶元素的值可用 _______________ 表示。 7、一棵高度为 5 的二叉树中最少含有 _________ 个结点，最多含有 ________ 个结点。 8、在无向图的邻接表中，每个结点被称为 ____________ ，通常它包含三个域：一是 _____________ ；二是 ___________ ；三是 _____________ 。 9、在一个索引文件的索引表中，每个索引项包含对应记录的 _________ 和 ___________ 两项数据。 10、假定一棵树的广义表表示为 A （ B （ C ， D （ E ， F ， G ）， H （ I ， J ））），则树中所含的结点数为 _________ 个，树的深度为 _________, 树的度为 ________, 结点H 的双亲结点为 ________, 孩子结点为 _______________ 。 11、在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为 _________, 整个堆排序过程的时间复杂度为 ________________ 。 12、二维数组A[10][5]（下标从0开始）采用行序为主方式存储，每个元素占4个存储单元，并且A[5][3]的存储地址是1000，则A[8][2]的地址是。 ，则Head(Head(Tail(A)))= 。 三、简答与运算题（每小题 6 分，共 30 分）
ONE. Single-Choice 1．In the following data structure, ( ) is linear structure. A．Forest B．Stack C．Graph D．Binary Tree 2．The Linked List is designed for conveniently ( ) data item. A．getting B．inserting C．finding D．locating 3．In the four choices, ( ) is not the principles that algorithm designing must obey. A．Correctness(正确性) B．Readability(可读性) C．Robustness(健壮性) D．Cyclicity(周期性) 4．Assume a sequence list as 6，5，4，3，2，1 is pushed in a stack, an impossible output sequence list is ( ). A．3，4，6，5，2，1 B．4，5，3，1，2，6 C．5，4，3，6，1，2 D．2，3，4，1，5，6 5．A stack is a structure that follows the principle of ( ). A．First-In/First-Out B．Lirst-In/Last-Out C．Last-In/First-Out D．Random In and Out 6．Removing the data item at index i in an array with n items, ( ) items need to be shifted(移动) left one position. A．n-i B．n-i+1 C．i D．n-i-1 7．There is an algorithm with inserting an item to a ordered SeqList(顺序链表) and still keeping the SeqList ordered. The computational efficiency of this inserting algorithm is ( ). A．O(log2n) B．O(1) C．O(n) D．O(n2) 8．The addresses which store Linked List ( ). A．must be sequential B．must be partly sequential C．must be no sequential D．can be sequential or discontinuous 9．According to the definition of Binary Tree, there will be ( ) different Binary Trees with 3 nodes. A．6 B．5 C．4 D．3 10．The depth of a Binary Tree is 5, it will have ( ) nodes at most. A．31 B．32