数据结构试题合集.doc

数据结构试题(B) 姓名_ 学号_ 班级_ 分数_一 选择填空（每空1分，共20分） 1 设有100个结点，用二分方法查找时，最大的比较次数是_。 (A) 25 (B) 50 (C) 10 (D) 72 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_存储方 式节省时间。 (A)单链表 (B)双向链表 (C)单循环链表 (D)顺序表 3 已知数据表A中每个元素距其最终位置不远，则采用_排序算法最省时间。 (A)堆排序 (B)插入排序 (C)直接选择排序 (D)快速排序 4 n个顶点的无向图的的邻接表中结点总数最多有_个。 (A) 2n (B) n (C) n/2 (D) n(n-1) 5 设连通图G的顶点数为n，则G的生成树的边数为_。 (A) n-1 (B) n (C) 2n (D) 2n-1 6 在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立图的 算法的时间复杂度为_。 (A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3) 7 快速排序算法在最好情况下的时间复杂度为_。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(log2n)8 以知一棵二叉树的前序和中序序列分别为ABDEGCFH 和DBGEACHF 则该二叉树 的后序序列为 _。 (A) GEDHFBCA (B) DGEBHFCA (C) ABCDEFGH (D) ACBFEDHG 9 线索二叉树中指向某结点的指针为D，该结点没有左孩子的条件是_。 (A) D-Lchild=NULL (B) D-Rchild=NULL (C) D-Ltag=0 (D) D-Ltag=110下列算法中，某一轮结束后未必能选出一个元素放在其最终位置上 的是_。 (A)堆排序 (B)冒泡排序 (C)直接插入排序 (D)快速排序 11 将新元素插入到链式队列中时，新元素只能插入到_。 A 链头 B 链尾 C 链中 D 第i 个位置 （i=1且i=0)个 _的有限序列。 A 字符 B 表元素 C 数据元素 D 数据项15 从逻辑上，可以将数据结构分为_两类。 A 动态表和静态表 B 顺序结构和链式结构 C 线性结构和非线性结构 D 动态结构和静态结构16 设无向图的顶点个数为n，则该图最多有_条边。 A n-1 B n(n-1)/2 C n(n+1)/2 D n17 稀疏矩阵的压缩存储可以采用_方式。 A 三元组表 B 哈希表 C双向链表 D 邻接表18 深度为5的满二叉树有_个结点。 A 32 B 15 C 31 D 16 19 二分（折半）查找有序表（2，3，5，10，12，20，30，32，40，45 ）， 若查找元素30，则被比较的依次 为_。 A 20，32，30 B 12，32，20，30 C 12，32，30 D 32，40，4520 算法应具的特点不包括_。 A 确定性 B 可行性 C 一一对应性 D有输入、输出 二 问题求解（每小题6分，共24分）1 给定下列网络G： 1）求最小生成树，画出逻辑图；2）画出G的邻接矩阵和邻接表。ABCEF122049682 已知下图为一棵二叉排序数，各结点的值依次为19，请标出各结点的值。 3 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都 集中到对角线以上？试举一例加以说明。4 找出所有二叉树，其结点在下述两种次序之下，恰好都以同样的顺序出现： a) 前序和中序；b) 前序和后序 三 简述下述算法的功能（每小题6分，共18分）（1）void a1 ( stack &s) int i, n, a255 ; n = 0 ; while ( ! stackempty(s) ) n+ ; pop ( s, an) ; for ( i = 1; inext) q=head ; head=head-hext; p=head ; while (p-next) p=p-next ; p-next=q ; q-next=NULL ; 四、算法设计（每题19分，共38分）1 设Hash函数为H(K)=K%14，K为关键字，%为取模运算，用线性探测再散列处理冲突，在地址范围015的散列区中，试用关键字序列（19，27，26，28，29，40，64，21，15，12，42，41）构造Hash表，要求：（1）画出该Hash表的存储结构图（2）若查找关键字40，必须依次与表中哪些关键字比较大小？（3）设每个关键字查找概率相等，试求查找成功时的ASL。2 试设计一个非递归算法把二叉树的叶结点按从左到右的顺序连成一个单链表，二叉树用二叉链表存储，链接时叶子结点的rchild 域用做单链表的指针。 算法所涉及的结构如下： typedef struct bnode elementype info ; struct bnode *lchild, * rchild ; bnode, bitree ; / 结点类型和指向二叉树的指针的类型 typedef struct seqstack bitree data maxsize ; / 栈的最大容量为 maxsize int top ; seqstack ; / 定义顺序栈类型 参 考 答 案 一 选择填空 1D 2D 3B 4D 5A 6A 7C 8B 9D 10C11B 12C 13D 14C 15C 16B 17A 18C 19B 20CABCEF20468二 问题求解 A B C E FA 0 12 0 4 0B 12 0 20 8 9C 0 20 0 0 0E 4 8 0 0 6F 0 9 0 6 0 5194236782T=0110010001211133 使得有向图中每条边始顶点的编号小于终顶点的编号。4 前序和中序 空树和具有所有的左链为空的二叉树。前序和后序 具有0个或1个结点的二叉树。三 简述下述算法的功能1 借用数组 a将栈中的元素逆置2 借用栈 t 删除栈s中所有值为 e的元素3 当单链表的长度大于等于2时，删除表中第一个 结点并将它插入到表尾。四、1 define max 12000 typedef struct node int data; int next; node, slinklistmax; hash (slinklist HT, int r) int i, j, k, n; for (i=0; i12000; i+) / 初始化 HTi.data = -1; HTi.next = -1; n = 0; for (k=0; klchild = NULL; p-rchild = NULL;h_leaf = p;if (t) / 当二叉树非空时 s.top = 0; s.datas.top = t;/ 初始化，根结点进栈 while (s.top !=0) /当栈非空时重复执行 t = s.data s.top; s.top -; / 退栈 if (t-lchild = NULL & t-rchild = NULL) / 将叶子结点插到单链表的尾部 p-rchild = t; p = p-rchild; / 指针p 向后流动 else / 非叶子结点继续扫描 if (t-lchild != NULL) / 若左子树非空，则进栈 s.top+; s.data s.top = t-lchild; if (t-rchild != NULL) / 若右子树非空，则进栈 s.top +; s.data s.top = t-rchild; 一选择题（每个2分，共20分）1 下列关于数据结构的叙述中，正确的是 （ ）A）数组是同类型值的集合B）递归算法的程序结构比迭代算法的程序结构更为精炼C）树是一种线性结构D）用一维数组存储二叉树，总是以先序遍历的顺序存储各结点2 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）A）94、32、40、90、80、46、21、69 B）32、40、21、46、69、94、90、80C）21、32、46、40、80、69、90、94 D）90、69、80、46、21、32、94、403 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是（ ）A）分块法 B）顺序法 C）二叉排序树 D）索引表查找4 以下关于广义表的叙述中,正确的是 （ ）A) 广义表是0个或多个单元素或子表组成的有限序列B) 广义表至少有一个元素是子表C) 广义表不可以是自身的子表D) 广义表不能为空表5 在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分法查找关键码值25,所需的关键码比较次数为A) 2 B) 3 C) 4 D) 56 高度为d(d0)的二叉树至少有_个结点（ ） A) d+1 B) 2d C).d D).d-17 下面有关散列表的叙述中,正确的是( ) A) 散列查找的时间与规模n成正比 B) 不管是开放地址法还是拉链法,查找时间都与装填因子有关。C) 开放地址法存在堆积现象，而拉链法不存在堆积现象。 D) 拉链法中装填因子必须小于。8对包含n个关键码的散列表进行检索，平均检索长度是（ ）A. O( log2n )B. O( n )C. O(n log2n )D. 不直接依赖于n9现有某个堆栈S,按顺序ABCD进栈，则出栈序列中不可能存在的是( )A）DCBA B) BACD C)CABD D)BADC10如果一棵二叉树结点的前序序列是A、B、C,后序序列是C、B、A,则该二叉树结点的对称序序列（ ）A) 必为A、B、C B) 必为A、C、BC) 必为B、C、A D) 不能确定 二填空题（每格1分，共20分）1. 结点在物理上的存储结构有四种，分别为_、_、_和_。2. 数据结构是指数据的组织形式，它一般包括三个方面，它们是_、_和_。3. 当待排序的序列已经或基本有序时，用快速排序方法对它进行排序，所需要的的时间复杂度为_，快速排序是_（稳定/不稳定）。4. 有一个链表，头结点为head，链表上某个结点的指针为p,现在已建立一个新结点q,把q插入到p之后的二句语句为代码为_和_。5. 高度为4的二叉树中，结点数最多为_，最少为_。6. 由n个终端结点生成的一颗Huffman树，度为的结点有_个。7. 假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表，其应的空间复杂度分别为_和_。8. 某个循环队列，其最大个数为m，其队首为front,其队尾为rear，则队列中元素的个数为_。9. 某个顺序表，表中元素的个数为n个，现把某个元素插入到表中某个位置i，则最好情况要移动_（次）,最坏情况要移动_次，平均移动次为_次。三分析题（每题5分，共30分）1.下面的算法是求稀疏矩阵的转置矩阵，采用三元组表示，a表示原矩阵，b是它的转置后稀疏矩阵的三元组表示。请完成该算法。（5分）/下面是算法所需要的数据类型 #define MaxSize 10000 /由用户定义 typedef int DataType； /由用户定义 typedef struct /三元组 int i，j；/非零元的行、列号 DataType v； /非零元的值 TriTupleNode； typedef struct /三元组表 TriTupleNode dataMaxSize； /三元组表空间 int m,n，t； /矩阵的行数、列数及非零元个数 TriTupleTable；/下面需要完成的算法void TransMatrix(TriTupleTable *b，TriTupleTable *a) /*a，*b是矩阵A、B的三元组表表示，求A转置为B /TransMatrix2.现有一个字符序列需要编码，该序列只含有a,b,c,d,e,f六个字符，其出现的机率分别为0.2,0.45,0.1,0.15,0.06,0.04，请用Huffman方法对它们进行编码，画出Huffman树，并求出其最短路径长度。并写出每个字符的二进制编码。要求，左子树的权值小于右子树，编码时，左子树取0 ，右子树取。(10分)3. 某个数组的初始状态为21,83,25,54,96,32,75,83,42是不是一个小大顶堆？如不是,则建立它的初始堆，用二叉树形表示，采用大顶堆。(分)4. 假设下面程序里的栈S已经初始化,经过下面这段程序处理后，屏幕上输出结果。（假设栈已经初始，且栈最多可以存放100个元素）(5分)void Demo(SeqStack *S)int i;int x;n=0;for(i=1;i5;i+)if（!StackFull(S)） Push(&S,i*5);else Error(Stack is full);while(!StackEmpty) x=Pop(&S);printf(%d n,x);5. 下面是一个有向图，分别用深度和广度遍历对它进行访问，输出其顶点序列，要求当有多个顶点可以同时访问时，先访问在字母表中前面字母所对应的结点。(5分)四设计题（每题15分，共30分）1. 有一个顺序有L，写一个函数InsertList在L中的第i个位置插入一个结点x值,该x的数据在主程序中输入。整个程序的结构如下，请完成整个程序，要符合C语言格式。#define ListSize 100 typedef struct StudInfoint number;/学号char name20;/姓名int yw;/语文int math;/数学int total;/总分;int order;/名次 STUDINFO; typedef STUDINFO DataType; typedef struct DataType dataListSize；/向量data用于存放表结点 int length； /当前的表长度 SeqList; main()int i,n;DataType x;printf(请输入实际人数:);scanf(%d,&n);for(i=0;irear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ ）6. 链表是一种采用 存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状（ ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以（ ）8 线性表在 情况下适用于使用链式结构实现。（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂（ ）9. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 i n=i n-i+1 不确定四、简答题（10分）1、已知如图所示的有向图，请给出该图的:顶点123456入度出度（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。 2、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：05U17X23V31Y47Z100120其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？五、写出下列程序段的输出结果（栈的元素类型SElem Type为char）。（1）void main( )Stack S;char x,y;InitStack(S);x=c;y=k;push(S,x); push(S,a); push(S,y);pop(S,x); push(S,t); push(S,x);pop(S,x); push(S,s);while(!StackEmpty(S) pop(S,y);printf(y); ;printf(x);结果：_（2）写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);结果：_6.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。五、算法设计（在下列算法的横线内填上适当的语句或表达式。）1、直接选择排序void selectsort (int R ) / 按递增序对R 0 Rn-1 进行直接选择排序 int i, j, k, temp ; for (i=0; i= ; i+) k=i ; for (j= ; jrear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ B ）6. 链表是一种采用 存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状（ D ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以（ B ）8 线性表在 情况下适用于使用链式结构实现。（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂（ C ）9. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 i n=i n-i+1 不确定四、1、 略2、 答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 五、1、 答：输出为“stack”。2、 答：输出为“char”。六、解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码六、阅读分析题（10分）指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。注：上题涉及的类型定义如下：# define LIST INIT SIZE 100# define LISTINCREMENT 10typedef struct Elem Type *elem; /存储空间基址Int length; /当前长度Int listsize; /当前分配的存储容量SqList;Status DeleteK(SqList&a, int i, int k)/本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if ( i1 | k a.length ) return INFEASIBLE; /参数不合法elsefor(count =