数据结构试题2

数据结构试题B 时间：120分钟 满分：100分 一、 选择题(每小题1分，共20分)1以下数据结构中， 是线性结构。A）栈 B）树 C）二叉树 D）图2在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。A、选择排序B、冒泡排序 C、插入排序D、希尔排序3下面 是顺序存储结构的优点。A）存储密度大 B）插入运算方便 C）查找方便 D）适合各种逻辑结构的存储表示4用链式方式存储的队列，在进行插入运算时， 。A）仅修改头指针 B）仅修改尾指针 C）头、尾指针都要修改 D）头、尾指针可能都要修改 5从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 排序法。A）插入 B）选择 C）冒泡 D）都不是6二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是 。先序序列：EFHIGJK 中序序列：HFIEJKGA）E B）F C）G D）H7下面 方法可以判断出一个有向图中是否有环。A）深度优先遍历B）拓朴排序C）求最短路径D）求关键路径8下面关于串的叙述中， 是不正确的。A）串是字符的有限序列 B）空串是由空格构成的串C）模式匹配是串的一种重要运算 D）串既可以采用顺序存储，也可以采用链式存储9 的邻接矩阵是对称矩阵。A）有向图 B）无向图 C）AOV网 D）AOE网10 若在线性表中采用折半查找法查找元素，该线性表应该 。A）元素按值有序 B）采用顺序存储结构C）元素按值有序，且采用顺序存储结构 D）元素按值有序，且采用链式存储结构11在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）插入一个新元素时，需要从后向前依次后移 个元素。 A、n-i B、n-i-1 C、n-i+1 D、i12一个栈的入栈序列是12345，则栈的不可能的输出序列是 。A、23415B、54132 C、23145D、1543213从邻接矩阵可以看出，该图共有 顶点。A、9 B、3 C、6 D、114上题中，若是无向图，则有 条边。A、5 B、4 C、3 D、215n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 。A、inB、2*inD、2*in16向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素。A、64.5B、64C、63D、65175个顶点的有向图最多有 条弧。A、5 B、20 C、30 D、2518在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 。A、q-next=p-next; p-next=q; B、p-next=q-next; q=p;C、p-next=p-next; q-next=q; D、p-next=q-next; q-nxet=p;19对一个满二叉树，m个树叶，n个结点，深度为h，则有 。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-120假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为 。A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL二、判断题：（判断下列各题正误，正确的在题目后面的括号内写“对”，错误的在题目后面的括号内写“错”。每小题2分，共10分）（ ）1. 含尾指针的单链循环表可以被用于队列操作。（ ）2. 栈和队列都不是线性数据结构。 （ 对 ）3. 数据项是数据的最小单位。（而数据元素是基本单位）（ ）4. 数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。（ ）5. 完全二叉树不可以用顺序存储结构进行存储。三、填空题（每空2分，共10分）1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 O（N） ，在表尾插入元素的时间复杂度为 O（1） 。2、队列的插入操作在 队尾 进行，栈的删除操作在 栈顶 进行。3、设字符串S1=ABCDEFG，S2=PQRST，则运算S=CONCAT（SUB（S1，2，LEN（S2），SUB（S1，LEN（S2），2）后的串值为 BCDEFEF 。四、回答下列问题（每小题8分，共40分）1 分别给出对下图进行深度优先和广度优先遍历的结果。2541368972已知序列（12，4，17，10，7，30），用冒泡排序法对其进行递增排序，写出每一趟的排序结果。3一批数据有如下的逻辑结构B=(K ,R),其中K=, R=r, r= ,试用图示法表示其逻辑结构。4已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。 5. 已知如下图所示二叉树，分别写出其前序、中序和后序序列。 A (5题图) B C D E F 五、编写算法（每小题10分，共20分）要求: 1、说明算法中使用的主要数据结构、变量；2、用C 1设有一个无头结点的单链表，编写子程序(或函数)统计其结点个数。2设有一向量A=（a1，a2， an-1，an），试设计一个算法