new数据结构复习题

1、数据结构复习题一、填空数据结构按物理结构可分为线性结构、 、 和集合。在单链表中，要删除某一指定的结点，必须先找到该结点的( )结点。对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是( )；在给定值x的结点后插入一个新结点的时间复杂度是( )。在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着 、1：N和 的联系。一棵有n个节点的满二叉树有 个度为1的节点。中缀表达式A-(B+C/D)*E的后缀表达式是 。具有n个顶点的完全无向图具有 条边，利用邻接矩阵表示的完全无向图具有 行，若无向图的邻接矩阵不存在边，则赋值_。平衡二叉树是每个结点的左、右子树的高

2、度至多相差_。一个有向图G中若有弧、和,图G的拓扑序列为_。直接插入排序的时间复杂度是，它(是/否？)稳定的。广义表(a, b), c, d)的表头是 ，表尾是 。限定在同一端进行插入、删除的线性表称为 ；该端称为 。内排序算法中空间复杂度最大的算法是。设顺序栈S为空，若6个元素入栈顺序为a1,a2,a3,a4,a5,a6，出栈顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少为。G是一个非连通无向图，共有28条边，则该图至少有_个顶点。一棵有n个结点满二叉树有个度为1的结点，有个分支结点和个叶子结点，该满二叉树的深度为。深度为6（根的层次为1）的完全二叉树至多有_结点，至少有_结点。

3、G是一个非连通无向图，共有28条边，则该图至少有_个顶点。从邻接矩阵A=中可以看出，该图共有_个顶点。如果是有向图，该图共有_条弧，如果是无向图，则共有_条边。一个有向图G中若有弧、和, 则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为_。二、选择题PS将s结点插入到p结点之后，实现语句为（）。A. s-next=p-next; p-next=s; B. (*p).next=s; (*s).next=(*p).next;C. s-next=p-next; p-next=s-next; D. s-next=p+1; p-next=s;将一棵有100个节点的完全二叉树从上到下，从左到右编号，

4、根节点的编号为1，则编号为49的节点的右孩子编号是（）。A97B98C99D100带头结点的单链表head为空的判定条件是( )。A. head=NULL B. head=NULL C. head-next=NULL D.head-next=NULL（）是C语言中 ”abcd321ABCD” 的子串。A.abcdB.321abC.“abcABC” D. “21AB”若广义表A满足head (A) = tail (A)，则A为 A. ( ) B. ( ( ) ) C. ( ( ), ( ) ) D. ( ( ), ( ), ( ) )有5个顶点的图，若为连通图，则至少有（ ）条边。A3B4C5D

5、6一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79有5个顶点的图，若为强连通图，至少有（ ）条边。A3B4C5D6下列不属于内排序算法的是（ ）。A. 归并排序 B. 基数排序 C. 拓扑排序 D. 堆排序已知广义表LS=(a,c), (b,d)，运算head和tail函数取出LS中元素b的运算是（）。Ahead(tail(LS) Btail(head(LS) Che

6、ad(tail(tail(LS) Dhead(head(tail(LS)线性链表中各链接点之间的地址（）。A.必须连续B.部分地址必须连续C.不一定连续D.以上答案都错误( )是C语言中”abcd321ABCD”的子串。 Aabcd B. 321AB C. abcABC“ D. “21AB“若串s=“software“，其子串的个数是( )。 A8 B. 9 C. 36 D. 37在一个单链表中，删除*p结点的直接后继结点，则执行（ ）。A. p=p-next B. p=p-next-next C. p-next=p D. p-next=p-next-next前序遍历和后序遍历结果相同的二叉树

7、具有（）特征。A.一般二叉树B.只有左子树的二叉树C.只有右子树的二叉树D.只有根结点的二叉树采用折半查找法查找长度为n的线性表，每个元素的平均查找长度为（）。A. O(n2) B. O(nlog2n) C. O(n) D. O(log2n)有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）A.35/12B.37/12 C. 39/12 D. 43/12有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值82的结点时，（）次比较后查找成功。A.1B.2C.4D.8从平均时间性能上看，(

8、)性能最佳，所需时间最省。A 堆排序 B归并排序 C基数排序 D 快速排序评价一个算法时间性能的主要标准是（ ）。A 算法易于调试 B 算法易于理解C 算法的稳定性和正确性 D 算法的时间复杂度若广义表A满足head (A) = tail (A)，则A为 A. ( ) B. ( ( ) ) C. ( ( ), ( ) ) D. ( ( ), ( ), ( ) )排序算法的稳定性是指（）。A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C. 排序算法的性能与被排序元素的数量关系不大D. 排序算法的性能与被排序元素的数量关

9、系密切哈希函数除留余数法，H(k)=k%m的m一般取（）。A自然数 B. 整数 C.素数 D. 有理数对线性表进行折半查找时，要求线性表必须（）。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序不带头结点的单链表head为空的判定条件是( )。A. head=NULL B. head=NULL C. head-next=NULL D.head-next=NULL有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值82的结点时，（ ）次比较后查找成功。A.1B.2C.4D.8循

10、环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front 和 rear，则当前队列中的元素个数是( ) A. (rear-front+m) % m B. rear-front+1 C. rear-front+1 D. rear-front若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( ) A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1将一棵有100个节点的完全二叉树从上到下，从左到右编号，根节点的编号为1，则编号为49的节点的右孩子编号是（）。A

11、97B98C99D100线性表是具有n个( )的有限序列。A. 数据元素 B. 字符 C. 数据 D.数据项若需在O(nlog2n)的时间内完成对数组的排序，且要求稳定，则可选择的排序方法是( )A、快速排序 B、堆排序 C、归并排序 D、直接插入排序在下述排序中，所需辅助存储量最多的是( )，所需辅助存储量最少的是( )，平均速度最快的是( )A、快速排序 B、归并排序 C、堆排序三、应用题线性表链式存储结构有单链表、循环链表、双向链表，试比较它们的优劣。一棵度为2的树与一棵二叉树有何区别？试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。设输入元素为1、2、3、p和a，输入次序为

12、123pa，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言的变量名。求下列中缀表达式后缀表达式1) 3+4/(25-6*5)*82) (1+2)*(8-2)/(7-4)给定一组关键字序列：11，78，10，1，3，2，4，21，(1)试生成二叉排序树，求查找成功的ASL(2)若向二叉排序树中插入元素12，删除元素3，则该二叉排序树的变化情况(3)试生成平衡二叉树，求查找成功的ASL(4)若向平衡二叉树中插入元素12，删除元素3，则该平衡二叉树的变化情况设哈希表长度为11，哈希函数 H(k)=k MOD 11, 若输入顺序为（18,10,21,9,6,3,16,2

13、5,7）,(1)处理冲突方法为线性探测法，请构造哈希表；(2) 处理冲突方法为拉链法，试构造链表。已知(29，18，25，47，58，12，51，10)，给出以下排序方法进行排序时的变化。(1)归并 (2)快速 (3)希尔用Dijkstra算法计算从源顶点1到其它顶点最短路径。设字符串为“ABEAACCDAACABBBBEAACDDE”，画出相应的Huffman树，并计算其WPL。用prim和kruskal算法分别构造下图所示网络的最小生成树。设有向图G如下图所示，(1)求该图的拓扑序列。(2) 添加哪条弧后，可以得到唯一的拓扑序列？已经有向网如下图所示，(1)求各顶点及各边的最早、最晚开始时间 (2)求关键路径模式串S=abcaabbabcab,根据KMP算法，求该模式串的next数组值。若目标串T=acbabcaabcaabb