发布时间 : 星期六 文章江苏技术师范学院 - 数据结构复习题及答案更新完毕开始阅读1f7315d4195f312b3169a577
一、单项选择题
1、向一个有255个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素。
A. 8 B. 127.5 C. 127 D.7 2、带头结点的单链表first为空的判定条件是：(B)
A. first==NULL B. first->link==NULL C. first->link==first D. first!=NULL
3、 设某线性链表的头结点指针为L, L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：(A)
A. p->next=L->next, L->next=p，L->data++; B. p->next=NULL, L->next=p, L->data++; C. L->data++, L->next=p->next, p->next=L; D. 以上都不是。
4、设A、B、C三个字符按先后顺序依次进栈，下面哪个序列为不合法的出栈序列：( D)
A. A B C
B. A C B
C. B A C
D. C A B
5、如下陈述中正确的是（ A）
A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 6、在二叉树的第4层上至多有多少个结点：(B) A. 10个
B. 8个
C. 16个 D. 以上都不是。
7、若一棵二叉树具有8个度为2的结点，则该二叉树的叶子个数是（ A ）
A. 9 B. 11 C. 7 D. 不确定
8、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )
A. e B. 2e C. n2－e D. n2－2e
9、5个不同的数据元素进行直接插入排序，最多需要进行（ B ）次比较。
A.8
B.10
C.14
D.25
10、设有关键码初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列
《数据结构》试卷 第 1 页 共 9 页
{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？（C）
A. 直接插入排序 B. 二路归并排序 C. 以第一元素为分界元素的快速排序 D. 基数排序
二、填空题
1、数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D，S)，其中D是数据元素的有限集；S是D上关系的有限集.
2、在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移n-i个元素。 3、队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 设S=”A;/document/Mary.doc”，则strlen(s)=20 “/”的字符定位的位置为3
5、在哈希造表过程中，处理冲突的方法主要有：开放定址法、再哈希法_链地址法、建立一个公共溢出区。
6、所谓稀疏矩阵指的是非零元很少(t< 7 在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为简单路径。 8. 一棵深度为6的满二叉树31_____个分支结点和____23_______个叶子。 9、对于n个记录的表进行2路归并排序，整个归并排序需进行log2n趟（遍）。 10、数据结构有如下四类基本结构：集合、_线性结构、树形结构、图形结构 11、在顺序表中插入或删除一个元素，需要平均移动__表中一半________元素，具体移动的元素个数与__表长和该元素在表中的位置_有关。 12. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 _栈顶_______。不允许插入和删除运算的一端称为___栈底_____。 13、_不包含任何字符（长度为0）的串__称为空串； 14、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址，则数组A的体积（存储量）为____288 B ___________。 15、一棵具有257个结点的完全二叉树，它的深度为__9 _ 三、判断题 ( )1、数据结构一般包括数据之间的逻辑结构，数据在计算机中的存储 《数据结构》试卷 第 2 页 共 9 页 方式和数据的运算三个方面。 ( ╳)2、单链表从任何一个结点出发，都能访问到所有结点 ( )3、线性表中的每个结点最多只有一个前驱和一个后继。 ( )4、一个n X n的对称矩阵，如果采用压缩存储，其容量为n(n+1)/2。 ( )5、 n个结点的树的各结点度数之和为n-1 ( ╳ )6、霍夫曼树一定是满二叉树。 ( ╳ )7、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。 ( )8、在有向图G中，所有结点的出度之和一定等于所有结点的出度之和 ( ╳)9、顺序查找法与折半查找法对存储结构的要求是：顺序查找与折半查找既适用于顺序表，也适用于链表 ( )10、散列表中碰撞的可能性大小与负载因子有关 ( ╳)11、 记录是数据处理的最小单位。 ( ╳)12. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 （ ╳)13. 栈和队列是一种非线性数据结构。 ( ╳ )14．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。 ( )15. 从逻辑结构上看，n维数组的每个元素均属于n个向量。 ( )16. 稀疏矩阵压缩存储后，必会失去随机存取功能。 (╳ )17.二叉树中每个结点的两棵子树的高度差等于1。 ( )18．强连通图的各顶点间均可达。 ( )19．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。 四、简答、应用题 1、 设n为正整数，给出下列程序段的时间复杂度。 void func(int n) { int k; k=1; while (k 《数据结构》试卷 第 3 页 共 9 页 k=k*3; } 解：k 所以T（n）=O(log3n) 或O（log (n)） 2、列出先序遍历能得到ABC序列的所有不同的二叉树。 3、已知某算法如下，试说明该算法实现的功能。 #define Max 100 void unknow(int num ,int r) {int st[Max],top=0; while (num!=0) { st[top++]=num%r; num=num/r; } while (top>0) cout << st[--top] << “ “; cout << endl; } 解：将十进制数num转换成r进制的数，并输出结果。 4、G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？ 解：设有一个顶点为独立的结点，其余结点为全连通图，则具有28条边的全连通图其有结点数为28<=n(n-1)/2,则n取满足该式的最小值为8，故该图至少有9个顶点。 5、 对于下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。 《数据结构》试卷 第 4 页 共 9 页