给出以下算法的时间复杂度

1、第1章绪论1、填空题 常见的数据结构有 结构，结构，结构等三 种。 常见的存储结构有 结构，结构等两种。数据的基本单位是，它在计算机中是作为一个整体来处理的。数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，和。2、应用题1、给出以下算法的时间复杂度.void fun(int n)(int i=1,k=100;while(in)(k=k+1;i=i+2;时间复杂度为。2、给出以下算法的时间复杂度.void fun2(int n)(int i=1,k=100;while(inext=p-next; p-next=s;p-next=s; s-next=p-next;s-next=p;

2、p-next=s-next;p-next=s; s-next=p;若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为()(1WiWn)A. O(0)B. O(1) C.O(n) D. O(n2)若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为()(1WiWn+1)A. n-iB. n-i+1 C. i D. n-i-13、判断题线性表中每一个元素都有一个前驱和一个后继。()4、程序设计题1、单链表的结点结构定义如下：struct LinkNode(LinkNode *next;int data;请根据述函数的功能写程序。(

3、10分)void Insert(LinkNode *h,LinkNode *s)(/h指向链表的头结点(即使链表中没有元素，头结点也存在。)链表中元素已经递增有序函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L 仍是一个有序表。顺序表的结构定义如下：#define ListSize 100/假定表空间大小为100struct SqList (int elemListSize;/数组elem用于存放表中的数据int length;/当前的表长度；/以上为顺序表的结构函数头定义如下void InsertIncreaseL

4、ist( SqList &L ,int x )(/3、单链表中结点的结构如下所示：typedef struct node( int data;struct node *next;node;请设计满足下述功能的函数。要求：建立带头结点的单链表H，要求函数从屏幕上读入m个整数，每读 入一个，便生成相应的结点，并且把它插入到链表H的尾部。函数形式为void CreateLinkList(node *H)。( 10 分)第3章栈和队列1、填空题 栈和队列在本质上都是。 栈的操作特点是。队列的操作特点是。 栈和队列是一种特殊的，栈的特点是；队 列的特点是。2、选择题消除递归不一定需要使用栈，此说法。A.

5、正确 B.错误 对于栈，输入序列为(1, 2, 3, 4),不可能得到的输出序列有。(A) (1, 2, 3, 4)(B)(4,3,2,1)(C) (1, 3, 4, 2)(D)(3,1,2,4)用单循环链表表示队列，正确的说法是 。可设一个头指针使入队、出队都方便；可设一个尾指针使入队、出队都方便；必须设头尾指针才能使入队、出队都方便；无论如何，只可能使入队方便。3、判断题 TOC o 1-5 h z 栈的特点是先进先出。()可以在队列的任意位置插入元素。() 递归程序化非递归程序必须用到栈。()如果进栈的序列为(1，2, 3, 4),则(4, 2, 3, 1)不可能是出栈序列。()在用顺序

6、表表示的循环队列中，可用标志位来区分队空或队满的条件。()第4章串1、选择题设有两个串p和q，求q在p中首次出现的位置的运算称作()A.连接 B.模式匹配C.求子串D.求串长2、判断题空串和空格串是同一个概念，二者没有区别。()第5章数组和广义表1、填空题二维数组在内存中存储可以有两种存储方式，一种是 优先存储，一种是 优先存储。设广义表 L =(),(),()。则 head(L)是； tail(L) 是; L 的长度是; L 的深度是。设广义表 L=(),(),() 则head(L)是； tail(L)是2、选择题在C语言中，如果有数组定义int A89；假定每个整型数据占2 字节，则数组元

7、素A44的地址是()。A. A+80 B. A+76 C.A+82 D.以上都不对广义表A= (a,b,(c,d),(e,(f,g),则下面式子的值为()；Head(Tail(Head(Tail(Tail(A)A. (g)B.(d) C.c D.d3、判断题在c语言中，多维数组的存储采取的是行优先的方式。()广义表在本质上也是线性表。()可以用三元组存储法来压缩存储稀疏矩阵。()已知广义表A=(a,b,c),(d,e,f),从A中取出原子e的运算是head(tail(head(tail(A)。()第6章树和二叉树1、填空题一棵62个叶结点的完全二叉树,最多有 个结点。若规定仅有根的二叉树的高度

8、为1,那么高为h的完全二叉树最多有-个结点，最少有 个结点。设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结 点数为，最小结点数为。设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点 数为，最小结点数为。2、选择题具有N个结点的完全二叉树的深度是。(A)l log2N(B) L log2N+1(C) l log2(N)(D) l log2N-1 设二叉树的树根为第一层，则第i层上至多有结点。1(B)2(C)2i-1(D)2i-13、判断题1.二叉树的左右子树次序是严格的，不能够任意改变。()深度为k深度为k的满二叉树的结点为2k-1。二叉树的三叉链表存储结构可以方便的

9、访问到双亲结点。4、应用题在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频 率分别为7,9,12,22,23,27。请回答下列问题：（1）什么是哈夫曼树？（3分）（2）根据题目所给频率值，画出相应的哈夫曼树。（11分）（3）给出各个字符对应的哈夫曼编码。（6分）（4）该段文字经过哈夫曼编码后，长度是多少。（4分）设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画 出对应的二叉树，并写出对应后序遍历序列。（15分）通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为0.23、 0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（

10、要求画出哈夫曼树， 并且把权值小的结点放在左边）。（共14分）某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D， C，H，F，G，E，请据此画出该二叉树，再给该树加上中序线索。（共15分）请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数 为 n2，则 n0=n2+1。（10 分）请按照孩子-兄弟表示法，将图1所示树转化为二叉树。（共14分）BEACFGD图1BEACFGD图1设二叉树如图2所示。分别写出它的先序遍 历、中序遍历、后序遍历序列。（共15分）图28.图2（1）写出如图所示二叉树的中序遍历结果。（8分）（2）画出二叉树的中序后继线索。（10分）9.

11、已知某二叉树的前序遍历序列为：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分）5、读程序写结果已知二叉树的结点结构如下:struct Node(int data;Node *lchild,*rchild;；某棵二叉树的形态如右图：根据要求解答下题：1、(共5分)int fun1(Node *root)(if(root=0) ret

12、urn 0;int l,r;l=fun1(root-lchild);r=fun1(root-rchild);if(l=r) return l+1;else return r+1;当root是指向结点A的指针时，函数fun1的返回值是多少？ (2分)函数fun 1的功能是什么？ (3分)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;当root是指向结点A的指针时，函数fun 1的返回值是多少？ (2分)函数fun 1的功能

13、是什么？ (4分)第7章图1、填空题有n个顶点的有向连通图最多有 条边，最少有 条边。 具有n个顶点的完全无向图有 条边，完全有向图有 条边。2、选择题方法可以判断出一个有向图中是否有环(回路)。(A)深度优先遍历(B )拓扑排序(C)求最短路径(D)求关键路径关键路径是指。从开始事件到终止事件路径长度最短的路径从开始事件到终止事件路径长度最长的路径从开始事件到终止事件活动最少的路径从开始事件到终止事件活动最多的路径方法 可以判断出一个有向图中是否有环(回路)。(A)深度优先遍历(B )拓扑排序(C)求最短路径(D)求关键路径3、判断题 具有n个顶点的有向图最多有n*（n-1）条边。（）在AO

14、V-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（）4、应用题1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序 列。（11分）2.请给出图1的所有最小生成树。（10分）图1请给出图2的所有拓扑排序序列。（16）4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。（共16 分）图25、请画出图3的所有最小生成树。（共10分）已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分）012分）0123456ABCDEF（1）请画出该图。（6分） （2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分）7、（本题总计7分） 构造该图

15、的最小生成树。5、程序设计题第8章动态存储管理1、填空题2、选择题3、判断题4、应用题5、程序设计题第9章查找1、选择题若在线性表中采用二分查找法查找元素，该线性表应该()。A.元素按值有序B.采用顺序存储结构元素按值有序，且采用顺序存储结构元素按值有序，且采用链式存储结构对二叉排序树进行 遍历，可以得到该二叉树所有结点构成的有序序列。前序 (B)中序 (C)后序 (D)按层次利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行()元素间的比较。A. 4次B. 5次C. 7次D.104.对二叉排序树进行遍历，可以得到该二叉

16、树所有结点构成的有序序列。(A)前序(B)中序(C)后序(D)按层次 散列函数有一个共同性质，即函数值应按()取其值域的每一个 值。A.最大概率 B.最小概率C.同等概率D.平均概率 一个哈希函数被认为是“好的”，如果它满足条件。哈希地址分布均匀保证不产生冲突所有哈希地址在表长范围内满足(B)和(C)哈希表的平均查找长度是 的函数。(A)哈希表的长度(B)表中元素的多少(C)哈希函数(D)哈希表的装满程度平均查找长度最短的查找方法是。（A）折半查找（B）顺序查找（C）哈希查找（4）其他2、判断题在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（） 对于折半查找，其前提条件是待查找序列只

17、要是有序的即可。（）3、应用题1.输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。（1）按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。（2）依此二叉排序树，如何得到一个从小到大的有序序列？2、若一棵排序二叉树的关键字输入序列为80，6，10，7，8，25，100，90， 请画出该二叉树。3.已知一组关键字为1,14,27,29,55,68,10,11,23，则按哈希函数H（key）=keyMOD 13和链地址法处理冲突来构造哈希表。（1）画出所构造的哈希表。（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。4、程

18、序设计题二叉排序树的结点结构如下所示：typedef struct node int data;struct node *lchild,*rchild;node；请编写在二叉排序树T中查找值为x的结点的非递归算法，如果查到，返回 指向该结点的指针，否则返回空。函数形式为：node* Search（node *T, int x）。（ 10 分）/已知整型数组A，从第一个单元（即A1）开始存储数据，且一共存储了 n个元素。要求编写折半查找元素e的过程。当数组中存在元素e时，返回其下 标，否则返回0。（10分）int BinarySearch（int *A,int n,int e）/已知整型数组A101，其中从A1到A100存储了 100个整数，试编写 函数int Find（int A101,int x），功能为从数组A中折半查找元素x，如果找 到则返回x所对应的下标，否则的话返回0。第10章内部排序1、填空题快速排序和堆排序的平均时间复杂度分别为 和2、选择题下面给出的四种排序法中（）排序法是不稳定性排序法。A-插入B.冒泡 C.二路归并D.堆排序从未排