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

资源描述

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

《给出以下算法的时间复杂度doc.docx》由会员分享，可在线阅读，更多相关《给出以下算法的时间复杂度doc.docx（19页珍藏版）》请在冰点文库上搜索。

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

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

第1章绪论

1、填空题

1.常见的数据结构有_________结构，_________结构，_________结构等三种。

2.常见的存储结构有_________结构，_________结构等两种。

3.数据的基本单位是_________，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，_________和_________。

2、应用题

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

voidfun（intn）

{

inti=1,k=100;

while（i

{

k=k+1;

i=i+2;

}

时间复杂度为_______________。

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

voidfun2（intn）

{

inti=1,k=100;

while（i

{

i=i*10;

k=k+1;

}

时间复杂度为_______________。

第2章线性表

1、填空题

1.线性表按照存储结构不同主要有两种实现方式，一种是_______________表，另一种是_______________表。

2.顺序表采用_______________访问机制对数据元素进行访问。

3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为:

①_____________________________；

②_____________________________；

4.在单向链表中，若要删除某个结点p，必须要找到_______________结点，才能实现该操作。

2、选择题

1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。

（A）n （B）2n－1 （C）2n （D）n-1

2.在单链表中，如果在结点p之后插入一个新结点s，其操作为。

（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个位置删除一个元素的算法的平均时间复杂度为（）。

（1≤i≤n）

A．O（0） B．O

（1） C.O（n） D．O（n2）

4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为（）。

（1≤i≤n+1）

A．n-i B．n-i+1 C.i D．n-i-1

3、判断题

1.线性表中每一个元素都有一个前驱和一个后继。

（）

4、程序设计题

1、单链表的结点结构定义如下：

structLinkNode

{

LinkNode*next;

intdata;

};

请根据述函数的功能写程序。

（10分）

voidInsert（LinkNode*h,LinkNode*s）

{//h指向链表的头结点（即使链表中没有元素，头结点也存在。

）

//链表中元素已经递增有序

//函数功能为将结点s插入到链表h中。

插入后链表仍然保持递增的顺序

}

2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

顺序表的结构定义如下：

#defineListSize100//假定表空间大小为100

structSqList{

intelem[ListSize];//数组elem用于存放表中的数据

intlength;//当前的表长度

};

//以上为顺序表的结构

//函数头定义如下

voidInsertIncreaseList（SqList&L,intx）

{

}

///////

3、单链表中结点的结构如下所示：

typedefstructnode

{intdata;

structnode*next;

}node;

请设计满足下述功能的函数。

要求：

建立带头结点的单链表H，要求函数从屏幕上读入m个整数，每读入一个，便生成相应的结点，并且把它插入到链表H的尾部。

函数形式为voidCreateLinkList（node*H）。

（10分）

第3章栈和队列

1、填空题

1.栈和队列在本质上都是_____________。

2.栈的操作特点是_____________。

队列的操作特点是_____________。

3.栈和队列是一种特殊的_____________，栈的特点是_____________；队列的特点是_____________。

2、选择题

1.消除递归不一定需要使用栈，此说法_______。

A.正确 B.错误

2.对于栈，输入序列为（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.用单循环链表表示队列，正确的说法是。

（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中首次出现的位置的运算称作（）

A．连接B．模式匹配C．求子串D．求串长

2、判断题

1.空串和空格串是同一个概念，二者没有区别。

（）

第5章数组和广义表

1、填空题

1.二维数组在内存中存储可以有两种存储方式，一种是_________优先存储，一种是优先存储。

2.设广义表L＝（（），（），（（）））。

则head（L）是；tail（L）是；L的长度是；L的深度是。

3.设广义表L＝（（），（），（（）））则head（L）是________；tail（L）是________。

2、选择题

1.在C语言中，如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（）。

A.A+80B.A+76C.A+82D.以上都不对

2.广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（）；

Head（Tail（Head（Tail（Tail（A）））））

A．（g） B.（d） C.c D.d

3、判断题

1.在C语言中，多维数组的存储采取的是行优先的方式。

（）

2.广义表在本质上也是线性表。

（）

3.可以用三元组存储法来压缩存储稀疏矩阵。

（）

4.已知广义表A=（（a,b,c）,（d,e,f））,从A中取出原子e的运算是head（tail（head（tail（A））））。

（）

第6章树和二叉树

1、填空题

1.一棵62个叶结点的完全二叉树,最多有________________个结点。

2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有________________个结点，最少有________________个结点。

3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为________________，最小结点数为________________。

4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为________________，最小结点数为________________。

2、选择题

1.具有N个结点的完全二叉树的深度是________。

（A）⌊log2N⌋（B）⌊log2N⌋+1

（C）⌊log2（N）⌋（D）⌊log2N⌋-1

2.设二叉树的树根为第一层，则第i层上至多有_______结点。

（A）1 （B）2 （C）2i-1 （D）2i-1

3、判断题

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分）

2.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。

（15分）

3.通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。

（共14分）

4.某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D，C，H，F，G，E，请据此画出该二叉树，再给该树加上中序线索。

（共15分）

5.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

（10分）

6.请按照孩子-兄弟表示法，将图1所示树转化为二叉树。

（共14分）

7.设二叉树如图2所示。

分别写出它的先序遍历、中序遍历、后序遍历序列。

（共15分）

（1）写出如图所示二叉树的中序遍历结果。

（8分）

（2）画出二叉树的中序后继线索。

（10分）

已知某二叉树的前序遍历序列为：

ABCDEFG和中序遍历序列为：

CBEDAFG。

请画出该二叉树。

10.

已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符，其出现次数分别为5，28，7，9，14，23，3，11次。

（1）请画出赫夫曼树（权值小的结点在左边）。

（15分）

（2）计算该树的带权路径长度。

（3分）

5、读程序写结果

已知二叉树的结点结构如下：

structNode

{

intdata;

Node*lchild,*rchild;

};

某棵二叉树的形态如右图：

根据要求解答下题：

1、（共5分）

intfun1（Node*root）

{

if（root==0）return0;

intl,r;

l=fun1（root->lchild）;

r=fun1（root->rchild）;

if（l>=r）returnl+1;

elsereturnr+1;

}

（1）当root是指向结点A的指针时，函数fun1的返回值是多少？

（2分）

（2）函数fun1的功能是什么？

（3分）

2、（共6分）

intfun2（Node*root）

{

if（root==0）return0;

intl=fun2（root->lchild）;

intr=fun2（root->rchild）;

returnl+r+1;

}

（1）当root是指向结点A的指针时，函数fun1的返回值是多少？

（2分）

（2）函数fun1的功能是什么？

（4分）

第7章图

1、填空题

1.有n个顶点的有向连通图最多有条边，最少有条边。

2.具有n个顶点的完全无向图有________条边，完全有向图有________条边。

2、选择题

1.__________方法可以判断出一个有向图中是否有环（回路）。

（A）深度优先遍历（B）拓扑排序

（C）求最短路径（D）求关键路径

2.关键路径是指__________。

（A）从开始事件到终止事件路径长度最短的路径

（B）从开始事件到终止事件路径长度最长的路径

（C）从开始事件到终止事件活动最少的路径

（D）从开始事件到终止事件活动最多的路径

3.方法可以判断出一个有向图中是否有环（回路）。

（A）深度优先遍历（B）拓扑排序

（C）求最短路径（D）求关键路径

3、判断题

1.具有n个顶点的有向图最多有n*（n-1）条边。

（）

2.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。

（）

4、应用题

1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。

（11分）

2.请给出图1的所有最小生成树。

（10分）

3.请给出图2的所有拓扑排序序列。

（16）

4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。

（共16分）

5、请画出图3的所有最小生成树。

（共10分）

6.已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。

（共12分）

图2

（1）请画出该图。

（6分）

（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。

（6分）

7、（本题总计7分）

构造该图的最小生成树。

5、程序设计题

第8章动态存储管理

1、填空题

2、选择题

3、判断题

4、应用题

5、程序设计题

第9章查找

1、选择题

1.若在线性表中采用二分查找法查找元素，该线性表应该（）。

A．元素按值有序 B．采用顺序存储结构

C．元素按值有序，且采用顺序存储结构

D．元素按值有序，且采用链式存储结构

2.对二叉排序树进行_________遍历，可以得到该二叉树所有结点构成的有序序列。

（A）前序（B）中序（C）后序（D）按层次

3.利用逐点插入法建立序列（51，71，43，81，74，20，34，45，64，30）对应的二叉排序树以后，查找元素34要进行（）元素间的比较。

A．4次 B．5次 C.7次 D．10

4.对二叉排序树进行____________遍历，可以得到该二叉树所有结点构成的有序序列。

（A）前序（B）中序（C）后序（D）按层次

5.散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。

A.最大概率 B.最小概率 C.同等概率 D.平均概率

6.一个哈希函数被认为是“好的”，如果它满足条件_________。

（A）哈希地址分布均匀

（B）保证不产生冲突

（C）所有哈希地址在表长范围内

（D）满足（B）和（C）

7.哈希表的平均查找长度是__________的函数。

（A）哈希表的长度（B）表中元素的多少

（C）哈希函数（D）哈希表的装满程度

8.平均查找长度最短的查找方法是____________。

（A）折半查找（B）顺序查找（C）哈希查找（4）其他

2、判断题

1.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。

（）

2.对于折半查找，其前提条件是待查找序列只要是有序的即可。

（）

3、应用题

输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1）按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。

（2）依此二叉排序树，如何得到一个从小到大的有序序列？

2、若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。

已知一组关键字为{1,14,27,29,55,68,10,11,23}，则按哈希函数H（key）=keyMOD13和链地址法处理冲突来构造哈希表。

（1）画出所构造的哈希表。

（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。

4、程序设计题

1.二叉排序树的结点结构如下所示：

typedefstructnode

{intdata;

structnode*lchild,*rchild;

}node；

请编写在二叉排序树T中查找值为x的结点的非递归算法，如果查到，返回指向该结点的指针，否则返回空。

函数形式为：

node*Search（node*T,intx）。

（10分）

///////////////

2.已知整型数组A，从第一个单元（即A[1]）开始存储数据，且一共存储了n个元素。

要求编写折半查找元素e的过程。

当数组中存在元素e时，返回其下标，否则返回0。

（10分）

intBinarySearch（int*A,intn,inte）

//////////////

3.已知整型数组A[101]，其中从A[1]到A[100]存储了100个整数，试编写函数intFind（intA[101],intx），功能为从数组A中折半查找元素x，如果找到则返回x所对应的下标，否则的话返回0。

第10章内部排序

1、填空题

1.快速排序和堆排序的平均时间复杂度分别为________和________。

2、选择题

1.下面给出的四种排序法中（）排序法是不稳定性排序法。

A．插入 B．冒泡 C．二路归并 D．堆排序

2.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。

（A）插入（B）选择（C）希尔（D）二路归并

3.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为______排序法。

（A）插入（B）选择（C）谢尔（D）二路归并

3、判断题

1.从平均性能而言，快速排序最佳，其所需时间最省。

（）

4、应用题

1.对于关键字序列{49，38，65，97，76，13}，回答下述问题。

（共12分）

（1）写出一趟冒泡排序的结果。

（6分）

（2）写出一趟快速排序的结果。

（6分）

第11章外部排序

第12章文件

展开阅读全文