数据结构-进栈出栈和排序习题集

《数据结构-进栈出栈和排序习题集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、填空题：（每空1分，共10分）1.数据的存储结构种类包括　①。2.分析以下部分代码的时间复杂度用大O表示法为②。inti=1;s=0;while(i<=n){s+=i;i=i+2;}3.队列是一种③的特殊的线性表。4.线性表的顺序存储结构通常可采用④和⑤两种访问方式。5.设一棵完全二叉树有700个结点，则共有⑥个叶子结点。6.将一个长度为n的顺序表的第i个元素删除时，只需前移⑦个元素。7.设数组a[1…10,1…20]的起始地址为100，每个元素占4个存储单元，若以行序为主序顺序存储，则元素a[3,5]的存储地址为　　　⑧　　　。8.

2、排序方法的稳定性是指⑨。9.对有序顺序表（3，8，10，25，29，45，55，77，85，99）采用折半查找，若查找表中元素10，它将依次与表中元素⑩比较大小。10.数据的存储结构主要包括。11.表达式求值是应用的一个典型例子。12.下面程序段的时间复杂度是。for(j=0;j＜n;j++)a=a+j；13.空串与空格串的区别在于：。14.单链表表示法的基本思想是用表示结点间的逻辑关系。15.在图1所示的树中，结点G的子孙结点有。16.在有n个顶点的连通图中，至少有条边。17.根据二叉树的定义，具有三个结点的二叉树有种不同的形态，分别是

3、。18.排序方法的稳定性是指。19.设有一稠密图G，则G采用存储较省空间。20.将一个长度为n的顺序表的第i个元素(1≤i≤n)删除时，需向前移动个元素。21.设数组a[1…10,1…20]的基地址为100，每个元素占4个存储单元，若以列序为主序顺序存储，则元素a[6,16]的存储地址为　　　　　　。22.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。23.数据的逻辑结构包括、和三种基本结构。24.表达式求值是应用的一个典型例子。25.下面程序段的时间复杂度是。i=1；while(i＜=n){t=t+1；i++；}26.空串

4、与空格串的区别在于：。27.单链表的基本思想是用表示结点间的逻辑关系。28.树的度是指。29.交换排序的方法主要包括。30.在有n个顶点的简单无向图中，最大可有条边。31.深度为7（根的层次号为1）的完全二叉树至少有___________个结点。32.图的存储方式主要有。33.将一个长度为n的线性表的第i个元素(1≤i≤n)删除时，需向前移动个元素。34.设数组a[0…10,0…20]的基地址为100，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[6,15]的存储地址为　　　　　　。35.查找表要采用折半查找，必须满足的条件是

5、。36．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_______的数量级相同。37．在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_________。38．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。19．设s=″IAMAATHLETE″,t=″GOOD″，则执行下列串操作序列之后得到的sub1为________。substr(sub1,s,5,2)；substr(sub2,s,6,8);strcpy(t1,t);strcat(

6、t1,sub2);strcat(sub1,t1);40．广义表的深度是指_______。41．一棵含999个结点的完全二叉树的深度为_______。42．含n个顶点的无向连通图中至少含有______条边。43．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为______。二、选择题：1.数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的和运算的学科。A.数据B.算法C.运算D.关系2.算法分析的目的是。A.找出数据结构的合理性B.研究算法中的

7、输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性3.线性表的顺序存储结构是一种结构。A.随机存取B.顺序存取C.索引存取D.HASH存取4.顺序表和链表均适用于查找。A．随机B．二分法C．顺序，也能二分法D．顺序5.在一个无向图中，顶点的度的和等于边的条数的倍。A．1／2B．lC．2D．46.一组记录的关键字为{8，2，5，4，7，9}，则利用堆排序的方法建立的初始堆(大顶堆)为。A．9，8，7，5，4，2B．9，7，8，4，2，5C．9，7，8，4，5，2D．9，8，7，4，5，27.若在线性表中采用折半查找法查找

8、元素，该线性表应该。A．元素按值有序B．元素按值有序，且采用顺序存储结构C．采用顺序存储结构D．元素按值有序，且采用链式存储结构8.二叉树是非线性数据结构，所以。A.它不能用顺序存储结构存储;