数据结构习题

数据结构习题一、填空题1、算法应具有的五个特性，分别为输入，输出，，及。2、对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。3、设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈至少应能存放个元素。4、串的两种最基本的存储方式是、。5、具有10个顶点的有向图，边的总数最多为。6、INDEX（‘DATASTRUCTURE’，‘STR’）=________。（INDEX为子串定位）7、一棵有n个结点的满二叉树有个度为1的结点、有个分支（非终端）结点和个叶子。8、堆排序的算法时间复杂度为。在数据表有序时，快速排序算法的时间复杂度是。9、数据结构是研讨数据的____________和____________，以及它们之间的相互关系，并对与这种结构定义相应的______________。10、数据结构中评价算法的两个重要指标是：和。11、栈中存取数据的原则，队列中存取数据的原则。12、链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的。13、如果一个函数，则称这个函数是一个递归函数。14、具有10个顶点的无向图，边的总数最多为。15、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次，当使用监视哨时，若查找失败，则比较关键字的次数为____。16、已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。17、下列程序段的时间复杂度为________________。product=1;for(i=n;i>0;i--)for(j=i+1;j<n;j++)product*=j;18、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用是________________。19、在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___________运算。20、如果排序过程不改变___________之间的相对次序，则称该排序方法是稳定的。21、一棵含999个结点的完全二叉树的深度为_______。（根结点记为1）22、在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。23、在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________。二、单项选择题1、设有一个递归算法如下：intfact(intn){if(n<=0)return1;elsereturnn*fact(n-1);}下面正确的叙述是（）。A、计算fact(n)需要执行n次递归B、fact(7)=5040 C、此递归算法最多只能计算到fact(8)D、以上结论都不对2、设单链表中结点结构为(data,next)。若想摘除结点*p的直接后继，则应执行下列哪一个操作（）。A、p->next=p->next->next; B、p=p->next;p->next=p->next->next;C、p->next=p->next; D、p=p->next->next;3、一个栈的入栈序列为a，b，c，则出栈序列不可能的是()。A、c,b,aB、b,a,cC、c,a,bD、a,c,b4、串的长度是指（）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A、9B、11C6、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A、O(n) B、O(n+e)C、O(n2)D、O(n3)7、在下面的排序方法中，辅助空间为O（n）的是()。A、希尔排序B、堆排序C、选择排序D、归并排序8、由3个结点可以构造出多少种不同的二叉树？（）。A、2B、3C、4D、59、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度()。A、必定快B、不一定C、在大部分情况下要快D、取决于表递增还是递减10、既希望较快的查找又便于线性表动态变化的查找方法是()。A、顺序查找B、折半查找C、索引顺序查找D、哈希法查找11、下述程序段中语句①的频度是（）s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)①s+=j;A、 B、C、 D、12、函数T1(n)=log2n，T2(n)=n,T3(n)=n2,T4(n)=2n，按它们在n→∞时的无穷大阶数排序时，最小的为（）。

A、log2n

B、n

C、n2

D、2n13、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的关系为()。A、i*(i-1)/2+jB、j*(j-1)/2+iC、i*(i+1)/2+jD、j*(j+1)/2+i14、某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A、空或只有一个结点B、任一结点无左子树C、高度等于其结点数D、任一结点无右子树15、一个有n个结点的图，最少有（）个连通分量。A、0B、1C、n-1D、n16、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）A、深度优先搜索算法 B、广度优先搜索算法C、求最小生成树的prim算法 D、拓扑排序算法17、在下面的排序方法中，辅助空间为O（n）的是()。A、希尔排序B、堆排序C、选择排序D、归并排序18、下面关于二分查找的叙述正确的是()。A、表必须有序，表可以顺序方式存储，也可以链表方式存储B、表必须有序且表中数据必须是整型，实型或字符型C、表必须有序，而且只能从小到大排列D、表必须有序，且表只能以顺序方式存储19、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A、O(n) B、O(n+e)C、O(n2)D、O(n3)三、简答题1、什么是栈的上溢和下溢？2、设有串A=””,B=”mule”,C=”old”,D=”my”，写出下列操作的结果。（1）substr(B,3,2)（2）insert(B,1,A)（3）replace(C,2,1,”k”)Substr为求子串，insert为子串插入，replace为子串替换。3、在图下图所示的各无向图中：(1)找出所有的简单环。

(2)哪些图是连通图?对非连通图给出其连通分量。

(3)哪些图是自由树(或森林)?4、简单叙述解决散列表冲突的两种方法，及其优缺点。5、完成带头结点的单链表（结点中数据域记为data，指针域记为next）按值定位函数LOCATE（head，key）,head为头结点，key为关键字，并对所填语句进行说明。linklist*locate(head,key)

linklist*head;

datatyekey;

{linklist*p;

p=head®next;while(p!=①)

if(②!=key)

③;

elsebreak;

returnp;

}6、已知一颗二叉树的中序序列BDCEAFHG和后序序列DECBHGFA，试画出这颗二叉树。7、按行优先顺序画出四维数组A[2][3][2][3]所有元素在内存中的存储次序。8、对于下图的连通网络，请用Prim（普里姆）算法构造出最小生成树。（画出生成最小生成树的每一个步骤）9、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆，要求写出过程）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，85，40，77，80，60，66，98，82，10，2010、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?11、已知n阶方阵A，若其元素满足如下性质：aij=aji，0<=i,j<=n-1则称A为对称矩阵。存储时只需将上三角或下三角矩阵元素按行序优先的顺序（如图所示）存储在一个一维数组中，这样可节省将近一半的存储空间。给出你的存储方案及下标对应关系。12、使用迪杰斯特拉算法求出从V1点出发到其它个顶点的距离值和最短路径。要求写明步骤。A13、采用单循环链表存储一元多项式，多项式A=2+2X+5X3+2X4可以表示为下图的形式。试画出B=3+2X+4X2及A与B的多项式和C的表示图示。A14、设散列表的长度为13，散列函数为H(K)=K%13，给定关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试分别画出拉链法解决冲突时所构造的散列表，并求出在等概率情况下，查找成功和不成功的平均查找长度。15、线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。四、综合题1、假设用于通信的电文仅由8个字母组成，分别为a,b,c,d,e,f,g,h，对应的在电文中出现的概率为：7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码。2、已知被查找的有序表R中关键字序列为：05，13，19，21，37，56，64，75，80，88，92完成以下的二分查找算法。intBINSEARCH(R,K)/*在有序表R中进行二分查找，成功时返回节点的位置，失败返回-1*/tableR[];keytypeK;{intlow,mid,high;low=0;high=n-1;while(low<=high){①；if(K==R[mid].key)returnmid;if(K<R[mid].key)②;else③;}return(-1)}画出查找K=21和K=85的查找过程。假设在各节点查找等概率的条件下，猜测二分查找的平均查找长度（不用证明）。3、阅读下列算法并回答问题：（1）设数组L[1..8]的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用SuanFa(L,8)之后的L[1..8]中的元素值；（2）简述函数SuanFa的功能。voidSuanFa(intR[],intn){intx=R[1];intlow=1,high=n;while(low<high){while(low<high&&R[high]>=0)high--;if(low>high){R[low++]=R[high];while(low<high&&R[low]<0)low++;R[high--]=R[low];}}R[low]=x;}4、阅读下列算法，并回答问题：(1)已知以T为根指针的二叉树如图所示，写出执行SuanFa(T)之后的返回值；(2)简述算法SuanFa的功能。intSuanFa(BinTreeT){intd;if(!T)return0;d=SuanFa(T->lchild)+SuanFa(T->rchild);if(T->lchild&&T->rchild)returnd+1;elsereturnd;}5、设有向图邻接表定义如下：typedefstruct{VertexNodeadjlist[MaxVertexNum];intn，e；