《数据结构考试题》由会员分享，可在线阅读，更多相关《数据结构考试题（23页珍藏版）》请在金锄头文库上搜索。
1、一、单项选择1. 数据结构是一门研究非数值计算的程序设计问题中 ，数据元素的、数据信息在计算机中的A 以及一组相关的运算等的课程。 A 操作对象E.计算方法C.逻辑结构D.数据映象 A 存储结构E.关系C.运算D.算法2. 以下数据结构中, D 是线性结构。A .广义表E.二叉树 C.稀疏矩阵 D.串3. 从逻辑上可以把数据结构分为 C两大类。A 动态结构和静态结构E.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和构造型结构4. 以下数据结构中, D 是线性结构。A .广义表E.二叉树C.稀疏矩阵D.串5. 以下数据结构中, D 是非线性结构。A 栈E.二叉树C.队列D.字符串6.
2、数据结构DS(Data Struct)可以被形式地定义为DS= ( D, R),其中D是_B_的有限集合，R是D上的有限集合。 A 算法E.数据元素C.数据操作D.数据对象 A 操作E.映象C.存储D.关系7. 线性表的顺序存储结构是一种丄的存储结构,线性表的链式存储结构是一种的B存储结构。A .随机存取E.顺序存取 C.索引存取 D.散列存取8. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_BA. 正确B.不正确9. 下面那一条是顺序存储结构的优点？ (A)A .存储密度大B.插入运算方便C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示10. 线性表采用链式存储结构时,要求内存中
3、可用的存储单元的地址 .A .必须是连续的B.部分地址必须是连续的C. 一定不连续D.连续和不连续都可以,插入一个元素所需要移动元素的平均次数为11. 表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时 E,删除一个元素所需要移动元素的平均次数为AA. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/212. 带头结点的单链表head为空的判定条件是_B。A. head= =NULLB. head- next= =NULLC. head- next= =headD. head!=NULL13. 在一个单链表中,若删
4、除p所指向结点的后继结点,则执行_A_A. p-n ext= p-n ext- n extB. p=p-n ext; p-n ext= p-n ext- nextC. p= p-n ext- n extD. p= p-n ext14. 若已知一个栈的入栈序列是1， 2， 3,A. iB. n=i C. n-i+1，n,其输出序列为p1, p2, p3,，pn,D.不确定若 p1= n,贝U pi 为 C 015. 设栈的输入次序为：1 , 2, 3, 4, 5,则不可能是其出栈序列A. 54321 B. 45321 C.43512 D. 1234516. 一个涕归算法必须包括BA.递归部分B.
5、终止条件和递归部分C.迭代部分D.终止条件和迭代部分17. 用链接方式存储的队列,在进行删除操作时 DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18. 数组Am存放循环队列的元素，其头尾指针分别是front和rear,则当前队列的元素个数是A. (rear-fro nt+m)%m B. (fron t-rea 叶m )%mC. fron t-rear+1 D. rear-fr on t+119. 栈和队列的共同特点_。A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点20. 一个栈的入栈序列a，b, c,A. edcba B. decba
6、d，e,贝U栈的输出序列是 一A.C. dceab D. abcde21. 栈的特点是_B_,队列的特点是_AA.先进先出B.先进后出22. 从一个栈顶指针HS的链表中删除一个结点,用x保存被删除的结点值，执行的语句为_CA. x=HS; HS=HS-n extB. HS=HS-n ext; x=HS-dataC节省存储空间D.降低运算的时间复杂度23. 在链队列Q中,插入s所指向的结点执行的语句为 _C_。A. Q.front-n ext=s;B. Q.rear- n ext=s; Q.rear=sC. s-n ext=Q.rear;Q.rear=sD. s-n ext=Q.fr on t;
7、Q.fro nt=s24. 空串与空格串是相同的，这种说法 _B_。A.正确B.不正确25. 下面关于串的叙述,哪一个是不正确的 _B_。A.串是字符的有限序列B.空串是由空格构成的串C.匹配模式是串的一种重要运算D.串可以采用链式存储结构26. 设有两个串p和q，求q在p中首次出现的位置的运算称作 _B_。A.连接B.模式匹配C.求子串D.求串长27. 若串s=software,其子串的数目为BA. 8B. 37 C. 36 D. 928. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内, 该数组按行存放时，数组元素A74的起
8、始地址为_C_。A. SA+141 B. SA+144 C. SA+222 D. SA+22529. 对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运算B.便于输入输出30. 在以下叙述中正确的是BA. 线性表的线性存储结构优于链表存储结构B. 二维数组可以看成是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出31. 广义表(a),a)的表头为C ,表尾为 C .A. ()B. a C. (a) D. (a)32. 已知广义表L=(x,y,z),a,(u,t,w),从L中取出原子项t的运算为_D.A. Head(Tail(Tail(L)B. Tail
9、(Head(Head(Tail(L)C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(Tail(Tail(L)33. 树最适合用来表示 BB.数据之间具有分支层次关系的数据D.无太多关系的数据元素A.有序的数据元素C.无序的数据元素34. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_BA. uwvtsB. vwutsC. wuvts D. wutsv35. 某二叉树的前序遍历结点访问顺序是 abdgcefh,中序遍历的结点访问顺序是 dgbaech，贝U其后序遍历的结点访问顺序是 _DA. bdgcefha B.
10、 gdbecfha C. bdgaechf D. gdbehfca36. 在一非空二叉树的中序遍历序列中，根结点的右边A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点37. 设m和n是一棵二叉树上的两个结点,在中序遍历,n在m前的条件是CA. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孙38. 深度为5的二叉树至多有_C_个结点。A. 16B. 32C. 31D. 1039. 由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_DA. 23B. 37C.46D. 4340. 利用二叉链表存储树
11、，则根结点的右指针是_CA.指向最左孩子B.指向最右孩子C.空 D.非空41. 下列存储方式中，哪一个不是树的存储形式？ D .A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法42. 在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍。A. 1/2B. 1C. 2D. 443. 具有n个顶点和多于n-1条边的无向图B.A.有可能是树B. 一定不是树C. 一定是树 D.以上答案都不对44. 具有6个顶点的无向图至少应有 _A_条边才能确保是一个连通图。A. 5B. 6C. 7D. 845. 无向图 G=(V,E),其中：V=a,b,c,d,e,f, E=(a,b),(a
12、,e),(a,c), (b,e),(c,f),(f,d),(e,d),则对该图进行深度优先遍历,得到的序列为:D_A. abecdf B. acfebd C. aebcfd D. aedfcb46. 下述几种排序方法中，要求内存量最大的是 _D_。A.插入排序B.选择排序C.快速排序D.归并排序47. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上 的方法，称为_C_。A.希尔排序 B.起泡排序C.插入排序D.选择排序48. 在待排序的兀素序列基本有序的前提下，效率最咼的排序方法是AA.插入排序B.选择排序 C.快速排序D.归并
13、排序49. 下列排序算法中,哪一个是稳定的排序算法？ B _A.直接选择排序 B.二分法插入排序C.希尔排序D.快速排序50. 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数AA. nB. 2n-1C. 2nD. n-1二、填空题1. 算法的五个重要特性是有穷性，确定性,可行性,输入和输出.2. 数据的树型结构和图（网）状结构合称非线性结构.3. 抽象数据类型的定义仅取决于它的一组逻辑特性,而与数据在计算机中的表示和实现无关.4. 评价算法质量的指标是 正确性，易读性健壮性高效性.5. 数据结构中评价算法的两个重要指标是:时间复杂度和空间复杂度6. 分析下面算法(程序段)，的时间复杂度是 O (mn) 。s=0;for (i=0;i n;i+)for (j=0;jprior=q-prior;q-prior- n ext=p;p-n ext=q;q_prior=
