资源描述
第1章 绪论1、填空题1.常见的数据结构有_线性_结构，_树形_结构，_图形_结构等三种。2.常见的存储结构有_顺序存储_结构，_链式存储_结构等两种。3.数据的基本单位是_数据元素_，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，_线性结构_和_非线性结构_。2、应用题1、给出以下算法的时间复杂度.void fun(int n)int i=1,k=100;while(in)k=k+1;i=i+2; 时间复杂度为_O（n）_。2、给出以下算法的时间复杂度.void fun2(int n)int i=1,k=100;while(inext=p-next_；_p-next=s_；4.在单向链表中，若要删除某个结点p，一般要找到_p的前趋_结点，才能实现该操作。2、选择题1. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 A 。(A)n (B)2n1(C)2n (D)n-12. 在单链表中，如果在结点p之后插入一个新结点s，其操作为 A 。（A）s-next=p-next; p-next=s;（B）p-next=s; s-next=p-next;（C）s-next=p; p-next=s-next;（D）p-next=s; s-next=p;3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(C )。(1in)AO(0) BO(1) C.O(n) DO(n2)4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为(B )。(1in+1)An-i Bn-i+1 C. i Dn-i-13、判断题1.线性表中每一个元素都有一个前驱和一个后继。（ ）4、程序设计题1、单链表的结点结构定义如下：struct LinkNodeLinkNode *next;int data;请根据述函数的功能写程序。void Insert(LinkNode *h,LinkNode *s)/h指向链表的头结点（即使链表中没有元素，头结点也存在。）/链表中元素已经递增有序/函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序LinkNode *p,*q;/q指向p的前驱q=h;p=h-next; while(p)if(p-datas-data) /寻找到插入点位置，插入sq-next=s; s-next=p; return;elseq=p; (1分)p=p-next; (1分)/当表中没有比s大的结点时，插入到表尾s-next=q-next; (2分)q-next=s; (2分)2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。顺序表的结构定义如下：#define ListSize 100 / 假定表空间大小为100struct SqList int elemListSize; / 数组elem用于存放表中的数据int length; / 当前的表长度;/以上为顺序表的结构/函数头定义如下void InsertIncreaseList( SqList &L ,int x ) int i;if ( L.length=ListSize) cout0 & L.elem i-1 x ; i-) L.elem i =L.elem i-1 ; / 比较并移动元素 L.elem i =x; /插入x L.length+; /表长增1 /3、单链表中结点的结构如下所示： typedef struct node int data; struct node *next;node;请设计满足下述功能的函数。要求： 建立带头结点的单链表H，要求函数从屏幕上读入m个整数，每读入一个，便生成相应的结点，并且把它插入到链表H的尾部。函数形式为void CreateLinkList(node *H)。参考程序：void CreateList(node *H)/H指向头指针int m,temp;coutm;/int i=1;node *tail; H-next=NULL;tail=H;while(i=m)coutplease input your number:temp;node *t=new node ;t-data=temp;t-next=tail-next;tail-next=t;tail=t;i+;第3章 栈和队列1、填空题1.栈和队列在本质上都是_线性表_。2.栈的操作特点是_后进先出_。队列的操作特点是_先进先出_。2、选择题1.消除递归不一定需要使用栈，此说法_A_。 A. 正确 B. 错误2.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有_D_。(A)（1，2，3，4）(B)（4，3，2，1）(C)（1，3，4，2）(D)（3，1，2，4）3.用单循环链表表示队列，正确的说法是 B 。 (A)可设一个头指针使入队、出队都方便；(B)可设一个尾指针使入队、出队都方便；(C)必须设头尾指针才能使入队、出队都方便；(D)无论如何,只可能使入队方便。3、判断题1.栈的特点是先进先出。（ ）2.可以在队列的任意位置插入元素。（ ）3.递归程序化非递归程序必须用到栈。（ ）4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（） 5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（） 第4章 串1、选择题1. 设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ）A连接 B模式匹配 C求子串 D求串长2、判断题1.空串和空格串是同一个概念，二者没有区别。（ ）第5章 数组和广义表1、填空题1.二维数组在内存中存储可以有两种存储方式，一种是_行_优先存储，一种是 列 优先存储。2.设广义表L(（），（），（）)。则head(L)是（） ；tail(L)是(（），（）) ；L的长度是3 ；L的深度是 3 。3.设广义表L(（a），（b），（c）) 则head(L)是_（a）_；tail(L)是_(（b），（c）)_。2、选择题1.在C语言中，如果有数组定义 int A89；假定每个整型数据占2字节，则数组元素A44的地址是（ A ）。A. A+80 B. A+76 C.A+82 D.以上都不对2.广义表A=（a,b,(c,d),(e,(f,g)）,则下面式子的值为(D )； Head(Tail(Head(Tail(Tail(A)A（g） B.(d) C.c D.d3、判断题1.在C语言中，多维数组的存储采取的是行优先的方式。（ ）2.广义表在本质上也是线性表。（ ）3.可以用三元组存储法来压缩存储稀疏矩阵。（ ）4.已知广义表A=(a,b,c),(d,e,f),从A中取出原子e的运算是head(tail(head(tail(A)。 ( )第6章 树和二叉树1、填空题1.一棵62个叶结点的完全二叉树,最多有_62*2=124_个结点。2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有_2h-1_个结点，最少有_2(h-1)_个结点。3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_2(k+1)-1_，最小结点数为_k+1_。4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为_2k-1_，最小结点数为_k_。2、选择题1.具有N个结点的完全二叉树的深度是_B_。(A) log2N (B) log2N +1 (C) log2(N) (D) log2N -12.设二叉树的树根为第一层，则第i层上至多有_C_结点。(A)1 (B)2 (C)2i-1 (D)2i-13、判断题1.二叉树的左右子树次序是严格的，不能够任意改变。（ ）2.若根为第一层，则深度为k的满二叉树的结点为2k-1 。 （ ）3.二叉树的三叉链表存储结构可以方便的访问到双亲结点。 （ ）4、应用题1.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：（1）什么是哈夫曼树？（3分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11分）（3）给出各个字符对应的哈夫曼编码。（6分）（4）该段文字经过哈夫曼编码后，长度是多少。（4分）参考答案如下：（1）答案为：带权路径长度最小的二叉树称为哈夫曼树。（3分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11分，每个结点1分）（3）给出各个字符对应的哈夫曼编码。（6分）a:1110 b:1111 c:110 d:00 e:01 f:10（4）该段文字经过哈夫曼编码后，长度是多少。（4分）(7+9)*4+12*3+(22+23+27)*2=244或者100+45+55+28+16=244fc287912222355162745100abed10000011112. 设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。（15分）参考答案如下：(1)画出二叉树（10分）错一个结点扣2分。 abcde（2）后序遍历序列为：bdeca （5分）3. 通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共14分）参考答案如下：为处理方便，关键字都乘以100，为23，20，32，12，13构造哈夫曼树为：（9分,每个结点1分）ABDEC010001111004357202325321213所以编码为：A：01 B：00 C：11 D：100 E：101 （5分，每个编码1分）4. 某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D，C，H，F，G，E，请据此画出该二叉树，再给该树加上中序线索。（共15分）CFBDGHE对应的二叉树为：（7分,每个结点1分）对应中序线索树为：（8分，每条线索1分）CFBDGHE55.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（10分）证明：令树中结点总数为N，度为1的结点个数为n1。则树中结点数满足下列公式：n0+n1+n2=N从度的角度来考虑，满足下列公式：2n2+n1+1=N从而得证：n0=n2+15. 请按照孩子-兄弟表示法，将图1所示树转化为二叉树。（共14分）解：（每个结点2分）ACBDEFGACBDEFG图1ABECFGDHIJ图26. 设二叉树如图2所示。分别写出它的先序遍历、中序遍历、后序遍历序列。（共15分）8. （1）写出如图所示二叉树的中序遍历结果。（8分）（2）画出二叉树的中序后继线索。（10分）（1）中序遍历结果：ADBCHFEG 共8分，每个字符1分（2）二叉树的中序后继线索如图 共10分，每个后继线索2分DACFGEHBDACFGEHBBCDFGAE9.已知某二叉树的前序遍历序列为：A B C D E F G和中序遍历序列为：C B E D A F G。请画出该二叉树。答案如下：10.已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符，其出现次数分别为5，28，7，9，14，23，3，11次。（1）请画出赫夫曼树（权值小的结点在左边）。（15分）（2）计算该树的带权路径长度。（3分）答案：此答案错误！（1）赫夫曼树构造如下。树中结点位置正确者，每个1分，共15分。30141679100422319118355828（2）该树的带权路径长度为 （5+3+7+8）*4+（11+14）*3+（23+29）*2=271 3分5、读程序写结果ABCDE已知二叉树的结点结构如下： struct Nodeint data; Node *lchild,*rchild;某棵二叉树的形态如右图：根据要求解答下题：1、 (共5分)int fun1(Node *root)if(root=0) return 0; int l,r;l=fun1(root-lchild); r=fun1(root-rchild); if(l=r) return l+1; else return r+1; （1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分)函数fun1的返回值是3。（2）函数fun1的功能是什么？(3分)函数fun1的功能是求二叉树的高度。2、 (共6分)int fun2(Node *root)if(root=0) return 0; int l=fun2(root-lchild ); int r=fun2(root-rchild ); return l+r+1; （1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分)函数fun1的返回值是5。（2）函数fun1的功能是什么？(4分)函数fun1的功能是求二叉树中所有结点的个数第7章 图1、填空题1. 有n个顶点的有向连通图最多有 n(n-1) 条边，最少有 n-1 条边。2.具有n个顶点的完全无向图有_2/n(n-1)_条边，完全有向图有_n(n-1)_条边。2、选择题1. _b_方法可以判断出一个有向图中是否有环（回路）。(A)深度优先遍历 (B)拓扑排序(C)求最短路径 (D)求关键路径2.关键路径是指_b_。(A)从开始事件到终止事件路径长度最短的路径(B)从开始事件到终止事件路径长度最长的路径(C)从开始事件到终止事件活动最少的路径(D)从开始事件到终止事件活动最多的路径7. 方法 b 可以判断出一个有向图中是否有环（回路）。(A)深度优先遍历 (B)拓扑排序(C)求最短路径 (D)求关键路径3、判断题1.具有n个顶点的有向图最多有n*(n-1)条边。 （t ）2.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（ t ）4、应用题1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。(11分)ABCDEFGHIJKA01111100000B00000010000C00000001000D00000000100E00000000010F00000000001G01000000000H00100000000I00010000000J00001000000K00000100000答案为：ABGCHDIEJFK (对一个1分)2. 请给出图1的所有最小生成树。（10分）aebdfc1238665图1 共两棵。第一棵为：(5分)错一条边扣1分。aebdfc12365aebdfc123665 第二棵为：(5分)错一条边扣1分。3. 请给出图2的所有拓扑排序序列。（16）图2abdfgceh答案如下：仅有两个第一个：abcdefgh (错一个字符扣1分)第二个：abcdegfh (错一个字符扣1分)4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。(共16分)12435678图2序列为：1、3、2、4、5、6、7、86. 已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分） 01234561A10110002B21001103C31000114D40100005E50110006F6001000图2(1) 请画出该图。（6分）（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分）（1） 请画出该图。（6分）错一个结点扣1分。ABCEFD（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分, 错一个字符扣1分）序列为：ABDECF7、（本题总计 7 分）构造该图的最小生成树。 aefgdbhc21111222243图的最小生成树如下 每条边1分，共7分 aefgdbhc2111122第9章 查找1、选择题1.若在线性表中采用二分查找法查找元素，该线性表应该( a )。A元素按值有序 B采用顺序存储结构C元素按值有序，且采用顺序存储结构D元素按值有序，且采用链式存储结构2.对二叉排序树进行_b_遍历，可以得到该二叉树所有结点构成的有序序列。(A) 前序(B)中序(C)后序(D)按层次3.利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行(a )元素间的比较。 A4次 B5次 C. 7次 D104.对二叉排序树进行_b_遍历，可以得到该二叉树所有结点构成的有序序列。(A) 前序(B)中序(C)后序(D)按层次5.散列函数有一个共同性质，即函数值应按(c )取其值域的每一个值。A.最大概率 B.最小概率 C.同等概率 D.平均概率6.一个哈希函数被认为是“好的”，如果它满足条件_d_。(A)哈希地址分布均匀(B)保证不产生冲突(C)所有哈希地址在表长范围内(D)满足(B)和(C)7.哈希表的平均查找长度是_d_的函数。（A）哈希表的长度 （B）表中元素的多少（C）哈希函数 （D）哈希表的装满程度8.平均查找长度最短的查找方法是_c_。（A）折半查找 （B）顺序查找 （C）哈希查找 （4）其他2、判断题1.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（ t ）2.对于折半查找，其前提条件是待查找序列只要是有序的即可。 （f ）3、应用题1.输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。(1)按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。(2)依此二叉排序树，如何得到一个从小到大的有序序列？2、若一棵排序二叉树的关键字输入序列为80，6，10，7，8，25，100，90，请画出该二叉树。解：二叉排序树为： （16分，每个结点2分）806100901072583.已知一组关键字为1,14,27,29,55,68,10,11,23，则按哈希函数H(key)=key MOD 13和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。（1）画出所构造的哈希表。 9个结点，每个1分011142723295568456789101023111112（2）在记录的查找概率相等的前提下，该表查找成功时的平均查找长度，ASL（142332）/9=16/9 2分4、程序设计题1.二叉排序树的结点结构如下所示：typedef struct node int data; struct node *lchild,*rchild; node；请编写在二叉排序树T中查找值为x的结点的非递归算法，如果查到，返回指向该结点的指针，否则返回空。函数形式为：node* Search(node *T, int x)。（10分）/2.已知整型数组A，从第一个单元（即A1）开始存储数据，且一共存储了n个元素。要求编写折半查找元素e的过程。当数组中存在元素e时，返回其下标，否则返回0。（10分）int BinarySearch(int *A,int n,int e)/参考程序如下：int BinarySearch(int *A,int n,int e)int low,high,mid;low=1;high=n; （1分）while(lowhigh)mid=(low+high)/2; （2分）if (e =Amid) （1分） return mid; （1分）else if(e Amid) （1分）high=mid-1; （1分）else low=mid+1; （1分）return 0; （1分）3.已知整型数组A101，其中从A1到A100存储了100个整数，试编写函数int Find(int A101,int x)，功能为从数组A中折半查找元素x，如果找到则返回x所对应的下标，否则的话返回0。第10章内部排序1、填空题1.快速排序和堆排序的平均时间复杂度分别为_o(nlog2n)-o(n2)_和_ o(nlog2n)_。2、选择题1.下面给出的四种排序法中( d )排序法是不稳定性排序法。A插入 B冒泡 C二路归并 D堆排序2.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 d 排序法。(A)插入(B)选择(C)希尔(D)二路归并3.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_a_排序法。(A)插入(B)选择(C)谢尔(D)二路归并3、判断题1.从平均性能而言，快速排序最佳，其所需时间最省。 （f ）4、应用题1. 对于关键字序列49，38，65，97，76，13，回答下述问题。（共12分）（1）写出一趟冒泡排序的结果。（6分）（2）写出一趟快速排序的结果。（6分）参考答案如下：（1）写出一趟冒泡排序的结果。（6分）38,49,65,76,13,97（2）写出一趟快速排序的结果。（6分）13,38,49,97,76,65
展开阅读全文