《《数据结构c语言》数据结构(甲)复习题.doc.pdf》由会员分享，可在线阅读，更多相关《《数据结构c语言》数据结构(甲)复习题.doc.pdf（16页珍藏版）》请在三一文库上搜索。
1、一. 是非题 I.数据结构可用三元式表示（D, S, P）?其中：D是数据对象，S是D上的关系，P是对D的 基本操作集。数据结构是二元式 2简单地说 , 数据结构是带有结构的数据元素的集合。 3判断带头结点的非空循坏单链表（头指针为L）中指针p所指结点是最后一个元素结点的条件 是：p-next=L o （t） 4线性表的链式存储结构具有可直接存取表中任一元素的优点。（0 5 线性表的顺序存储结构优于链式存储结构。 6.在单链表P指针所指结点之后插入S结点的操作是： P-next= S ; S- next = P-next；o （f）S- next = P-next; P-next= S ; 7
2、 对于插入、删除而言，线性表的链式存储优于顺序存储。（t） 8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（0 9.栈和队列是操作上受限制的线性表。（t） 10.队列是与线性表完全不同的一种数据结构。 II.队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。（D 12.栈和队列也是线性表。如果需要，可对它们屮的任一元素进行操作。 13.栈是限定仅在表头进行插入和表尾进行删除运算的线性表。 14.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的 特殊情形。（f）二叉树是有序树，树是无序的 15二叉树是一棵结点的度最大为二的树。子数有左右之分 16
3、 赫夫曼树屮结点个数一定是奇数。 17在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。（t） 18假设B是- 棵树，B是对应的二叉树。则B的后根遍历相当于的后序遍历。（f） 19.通常，二叉树的第i层上有2个结点。（0 至多有 20.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。（t） 21 二叉树的先序遍历序列屮，任意一个结点均处在其孩子结点的前面。 22由树结点的先根序列和后根序列可以唯一地确定一棵树。（t） 23邻接多重表可以用以表示无向图，也可用以表示有向图。无向图的链式存储结构 24 可从任意有向图中得到关于所有顶点的拓扑次序。（f） 25有向图的
4、十字链表是将邻接表和逆邻接表合二为一的链表表示形式。（t） 26关键路径是AOE网屮源点到汇点的最短路径。（f）最长路径 27连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。（f）有n-1条边的 图 不一定是生成树，要是连接这n个顶点的n-1条边 28 一个无向图的连通分量是其极大的连通子图。（t） 29十字链表可以表示无向图，也可用以表示有向图。 冇向图的一种链式存储结构 30邻接表可以表示有向图，也可以表示无向图。（t ） 31.二叉排序树的平均查找长度为0（logn）0（t） 32.二叉排序树的最大查找长度与（LOG2N）同阶。最好的情况logm 33选用好的HASH函数可
5、避免冲突。 34折半查找不适用于有序链表的查找。 35.对于目前所知的排序方法，快速排序具有最好的平均性能。（t） 36对于任何待排序序列来说，快速排序均快于冒泡排序。（f） 37在最坏情况下，堆排序的吋间性能是O（nlogn）,比快速排序好 38快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O （nlogn）。（f） 39.字符串是数据对象特定的线性表。 40.空串与空格串是相同的。 41.对于一棵ni阶的B树. 树中每个结点至多有m个关键字 . 除根之外的所有非终端结点至 少有m/2个关键字。(f) “关键宁”应为“子树” 42.当二叉排序树是一棵平衡二叉树时，其平均查找长度
6、为O(log2n)o (t) 43.广义表的表头和表尾都是广义表。 44二维数组是其数据元素为线性表的线性表。 选择题。 1从逻辑上可以把数据结构分成( c ) 。 A.动态结构和静态结构B.顺序组织和链接组织 C.线性结构和非线性结构D.基本类型和组合类型 2线性表1_在(b ) 情况下适于使用链表结构实现。 A.不需修改L的结构B.需不断对L进行删除、插入 C.需经常修改L中结点值D.L中含有大量结点 3带头结点的单链表L为空的判断条件是b 。 带头结点的循环链表L为空的判断条件是c。 A. L=null B. L-next=null C. L-next=L D. L!=null 4若顺序
7、表中各结点的查找概率不等，则可用如卜策略提高顺序查找的效率：若找到指定的结 点，将该结点与其后继 ( 若存在 ) 结点交换位置，使得经常被查找的结点逐渐移至表尾。以下 为据此策略编写的算法，请选择适当的内容，完成此功能。 顺序表的存储结构为： typedef struct ElemType *elem; /数据元素存储空间，0号单元作监视哨 int length; /表长度 SSTablc; int search_seq(SSTable ST,KeyType key) 在顺序表ST中顺序查找关键字等于key的数据元素。 若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。 ST
8、.elemO.key=key; i=ST.Icngth; while(ST.elemi. key! =key) f ; iff G ) ST.elemi -* ST.elemi+1 ； return i; A. i0 B. i=0 E. i卄F. i- C. i 2 ? 1 1 1 D? 0 - 3 - 4 |A 2 C-? 4 3 B ? 1 - 2 - ? 0 I A 4 A一2 A 1 根据存储结构依教材中的算法其深度优先遍历次序为（d ）。 广度优先遍历此序为（C ）。各强连通分量的顶点集为（h ）。 a: abcde ?b: edcba ?c: ecdab ? e: abc 及ed
9、f: be 及aed g: ab 及ced 下列查找方法屮 (a )适用于查找单链表。 ) B.x是y的右兄弟 D. x是y的子孙 当二叉树中有n个结点时，有（d ）个空指针。 C. n+1 D. n+2 深度优先遍历图使用了数据结构（b人而广度优先遍历图使用了数据结构（C ）o 数组B)栈C）队列D）线性表 d: ecadb? h: ac 及bed 适用于求图的最小代价生成树。（b ）能对图作广度优先遍历。 A）顺序查找B）折半查找C）分块查找D) hash查找 38下列算法中（c ） A）DFS 算法B） BFS 算法C） Prim 算法D） Dijkstra 算法 39关键路径是指在只有
10、一个源点和一个汇点的有向无环网中源点至汇点（c ）的路径。 a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小 40希表的查找效率取决于（d ）。 a:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是 41 在Hash 函数H（k）=k MOD m +，一般来说，m 应取（c ）。 A.奇数B.偶数C.素数D.充分大的数 42在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用a方法。 A.设置监视哨B.链表存贮C.二分查找D.快速查找 43静态查找表和动态查找表的区别在于（b ）o A.前者是顺序存储，而后者是链式存储 B.前者只能进行查找操作，
11、而后者可进行查找、插入和删除操作 C.前者只能顺序查找，而后者只能折半查找 D.前者可被排序，而后者不能被排序 44在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行（b ）次元素 比较。 A? Llog2（n）B. Llog2（n）J+l C. Llog2（n+l）J D. Llog2（n+l）J+l 45设输入序列为20,45,30,89,70,38,62, 19依次插入到一棵2? 3树中（初始状态为空）， 该B树为（b ）o再删除38,该B树为（f ）0 (30 62 ) (19, 20) ( 38 45 ) ( 70, 89 ) a: (38 ) (19 ) (30,38
12、 ) d: b: )(89 ) (62 ) (19, 20) (45 62) ( 89 ) (30 ) ( 62 ) ( 89 ) f: (30 45 ) (70 ) 46根据插入次序(80, 90, 100, 110, 85, 70, 75, 60, 72)建立二叉排序树。 图(a ) 是最终变化的结果。若仍以该插入次序建立平衡二叉树。图(c ) 是最 终变化的结果。 c: d: 47若有序表中关键字序列为：14, 20, 25, 32, 34, 45, 57, 69, 77, 83, 92。对其进行折半查找，则 在等概率情况下，杳找成功时的平均查找长度是(c 查找32时需进 行(c ) 次
13、比较。 A. 1 B. 2 C. 3 D. 4 48己知哈希表地址空间为A9,哈希两数为H(k)=k mod 7,采用线性探测再散列处理冲突。若依 次将数据序列：76,45,88,21,94,77,17存入该散列表屮，则元素17存储的下标为 (h ) ； 在等 概率情况下査找成功的平均査找长度为(C )o A. 0 B. 1 C. 2 D. 3 E.4 F. 5 G. 6 H. 7 49若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该 二叉树是 (c ) 。 A.二叉排序树B.赫夫曼树C.堆D.平衡二叉树 50当待排序序列的关键字次序为倒序时，若需为之进行正序排
14、序，下列方案中4为佳。 A.起泡排序B.快速排序 C.直接插入排序D.简单选择排序 51下列排序算法屮，( 算法可能会出现：初始数据有序时，花费的时间反而最多。 A.堆排序B.起泡排序C.归并排序D.快速排序 52在下列排序方法中， (c ) 方法平均时间复杂度为0(nlogn), 最坏情况下时间复杂度为0(n2)； ( d )方法所有情况下时间复杂度均为0(nlogn)o a.插入排序b.希尔排序c.快速排序d.堆排序 53已知- 组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42 60 a: b: 85 90 75 80 100 60 70 72
15、110 75 70 80 11 0 72 85 90 下列选择中（d ）是快速排序一趟排序的结果。（c ）是希尔排序 （初始步长为3）趟排序的结果。（a ）是初始堆（大堆顶）。 A） 86,75,77,58,42,19,56,35,4 Push ( S,T ); While ( !stackempty( S ) While ( gettop( S, p ) Pop ( S , p ); if ( _ ) _; push( S, p-rchild); return ok; 26( 算法填空 ) 下列算法试图完成在数组A中搜索有无关键字key,若有，返回数组下标，若无，返回在“ ” 处填上合适的内
16、容，完成该算法。 int BinaryScarch (keytype A , int low,int high, keytype key ) middle = (low+high) /2; if( ) return middle; if (key Amiddle) else return -1; /end of BinarySearch 27( 算法填空 ) 下列函数为堆排序中的堆调整过程( 调整H.rs的关键字，使H.rsm成为一小顶堆 ) 。请在 “ _ “处填上合适的内容，完成该算法。 Void heapadjust( heaptype H , int s , int m ) rc=H.
17、rs; for (j=2*s;j=m;j*=2) if (jm H.rs=H.rj; s=j; /heapadjust 图示结构题 1已知在电文中只出现频率为(5,26,7,23,20,19)的6个字符 , 画出你建的哈夫曼树，并给出其哈夫 曼编码。 2. 已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG 请画出该二叉树，并为之建立先序线索。 3己知某二叉树的先序遍历次序为：a,b,c,d,e,f,g冲序遍历次序为：b,a,d,f,e,g,c 画出该二叉树，并在该二叉树上建立屮序线索。 4某二叉树的中序遍历次序为BEGFDAC,先序遍历次序为ABDEFGC。 试画出该二
18、叉树，并为之建立中序线索( 图示之 )。 5已知某二叉树的后序遍历和中序遍历次序分别为FBEDGCA和FBADECG, 请构造并画出该二 叉树。 6设某一电文只出现a,b,c,d,e,f,g 7个字母；出现频率分别为30%, 10%,05%,04%, 13%, 18% 及 20%，请给出各字母的哈夫曼编码。 7将图示森林转换为二叉树，并对该二叉树先序全序线索化。 8将图示森林转换为二叉树，并对该二叉树屮序全序线索化。 9某二叉树的结点数据采用顺序存储表示如下: 10已知某有向图如图所示： 1)给出其十字链表存储结构 2)给出其深度优先遍历次序。 3)给出其广度优先遍历次序。 4)给出各强连通分
19、量。 11设输入序列为20,45,30,89,70,38,62,19,依次插入到一棵2? 3树中( 初始状态为 空)， 请画出该B树。 12右图为一棵3阶B 树。(20, 25) 1)画出在该树上插入元素15 / | 后的B 树。( 10, 14) (21) (35) 2)接着，再删除元素35,画出删除后的B 树。 13已知Hash函数为H (K) =K mod 13 , 散列地址为0?14,用线性探测再散列处理冲突, 给出关 键字(56, 34, 68, 23, 16, 70, 48, 35, 83, 12, 14, 57) 在散列地址的分布。并指出平均成功的查找长 度是多少？ 0 1 2
20、3 4 5 6 7 8 9 10 11 12 13 14 14根据插入次序(20, 30, 70, 60, 10, 100, 110, 90, 80。) 建立平衡的二叉排序树。 15设哈希表长为16,哈希函数为H(kcy)=kcy mod 13,用开放定址法的二次探测再散列处理冲突 ABCDEFGHI 0 1 2 345 6 7 8 910 11 12 13 14 15 16 17 18 19 ( 1)试画出此二叉树的图形表示。 (2)将此二义树看作森林的二义树表示，试将它还原为森林。 (dj=l 2, -l2, 22, -22, 32, -32)o 依次存入 12 个元素 :56, 82,
21、17,24, 36,21,83,96,13,34,57,50。请画 出它们在表中的分布情形。 16己知待排序序列为：25,12,9,20,7,31,24,35,17,10,试写出： (1) .堆排序初始建堆 (大顶堆 )的结果； (2) .以第一个元素为枢轴的快速排序一趟扫描的结果； (3) .希尔排序第一趟 (增量为5)的结果。 算法设计题 1设有一个带头结点、元素按值递增有序的单链表，结点的类型定义如下： typedef struct LNode int data; struct LNode *next; LNode, *LinkList; 编写算法，删除其中所有值相同的多余元素结点 2某
22、线性表屮元素以降序排列，现要插入一个元素X,插入后该线性元素仍保持降序。线性表采用 带头结点单链表方式存贮。请编写该插入算法。 3编写在一有序顺序表中插入数据元素X的算法INSERT (L, X)。 4写一算法 ,DeleteOinklist struct LNode *ncxt; LNode, *Linklist; 5写一算法，Contrary (linklist struct LNode *ncxt; LNode, *Linklist; 7写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。( 注: 不破坏A和B 的原有 结构.)Merge(Linklist A, Linklist
23、 B, Linklist 存储空间基址 int rear; 尾指针，若队列不空，指向队尾元素int length; 当前队列的长度，即元素 个数 SqQucuc; 试写出相应初始化、入队列和出队列的三个函数。 11二叉树用二叉链表存储表示。 typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 试编写销毁二叉树T的算法DestroyBiTree （ BiTree Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 试编写
24、算法，求元素值为x的结点的左孩子（返回x的左孩子的指针）。 13设计一算法，计算给定二叉树T屮度为2的结点个数。 14编一算法：按层序遍历二叉树T。 15试编写先序遍历二叉树T的递归算法PreorderBiTree （ BiTree &T ）。 16写出一个将树屮每个结点的左右孩子对换的算法 SWAPTREE(T) 即如: 原二叉树 T (A) / (B) (C) / / (D) (E) (F) (G) (H) 17二叉树用二叉链表存储表示。 试编写后序遍历二叉树T的递归算法PostorderB汀ree （ B汀ree T）。18写一个计算二叉 树中叶子结点个数的递归算法。 注释（不一定准确）一一独立观察员 转换后 SWAPTREE(T) I (A) / (C) (B) / (F) (E) (D) / / (H) (G)