数据结构习题.doc

数据结构习题1算法指的是（ ）。A 计算机程序 B. 解决问题的计算方法C 排序算法 D. 解决问题的有限运算序列。2. 从逻辑上可以把数据结构分为（ ）两大类。A. 动态结构、静态结构 B. 顺序结构、链式结构 C. 线性结构、非线性结构 D. 初等结构、构造型结构3. 算法分析的两个主要方面是( ) A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性 D. 数据复杂性和程序复杂性4. 程序段如下：sum=0； for(i=1;i=n;i+) for(j=1;j=n;j+) sum+；n为正整数，则其时间复杂度为（ ）。A. O(n） B. O(nlogn) C. O(n3) D. O(n2) 5. 下列属于非线性结构的是（）。（多选）A. 数组 B. 图 C. 队列 D. 线性表 E. 树6. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。 AO(0) BO(1) CO(n) DO(n2)7. 下面程序段的时间复杂度是( )。for(i=0;in;i+) for(j=1;jm;j+) Aij=0；A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)8. 下面程序段的时间复杂度是 （ ）。 for ( a=0 ; a x ; a + ) b=0 ; while ( b next=HL; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. p-next=HL-next; HL-next=p;13. 在一个单链表中,若q所指结点是p所指结点的直接前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。A. s-next=p-next; p-next =s; B. p-next =s; s-next =q; C. p-next =s-next; s-next=p; D. q-next =s; s-next =p;14. 在单链表中，指针p指向元素为x的结点，实现“删除x的直接后继结点”的语句是( )。A. p=p-next; B. p-next=p-next-next;C. p-next=p; D. p=p-next-next;15. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。(不带表头结点的单链表呢?) Ahead=NULL; Bhead-next=NULL; Chead-next= =head; Dhead!=NULL;16. 运行以下代码段后，x 和 y 的值分别等于（ ）。int x=10,y=20; InitStack(S); / 初始化栈Push(S,x); Push(S,y); / 进栈Pop(S,x); Pop(S,y); / 出栈A. 20和10 B. 10和20 C. 10和10 D. 20和2017. 以下叙述中正确的是（ ）。A. 串是一种特殊的线性表 B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串18. 栈的插入和删除操作在（ ）进行。A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置19. 一个递归算法必须包括（ ）。 A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分20. 设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳。 A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈21. 栈在（ ）中应用。A. 递归调用 B. 子程序调用 C. 表达式求值 D. A,B,C都对22. 对稀疏矩阵进行压缩存储主要目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度23. 设有三个元素X，Y，Z顺序进栈（进栈过程中允许出栈），下列得不到的出栈排列是( )。 AXYZ B. YZX C. ZXY D. ZYX 24. 有一个二维数组A1:6，1:8 ，每个数组元素用相邻的6个字节存储，存储器按字节编址，已知A的基地址是0。若按行存储，则A2，4的首地址是（ ）。(按列存储呢？) A. 200 B. 120 C. 66 D. 114 25. 最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是 （ ）。(队满呢？) A. (rear+1) % n=front B. rear=front Crear+1=front D. (rear-l) % n=front26. 树最适合用来表示( ) A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据27. 深度为6（根的层次为1）的二叉树至多有（ ）结点。A. 64 B. 32 C. 31 D. 6328. 设一棵二叉树的先序遍历和中序遍历所得序列分别是abdc 和 bdac ，则该树的后序遍历序列为（ ）。 A. abcd B. dbca C. cdba D. dbac29. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。2143A. 1/2 B. 1 C. 2 D. 430. 设有一AOV-网如右图所示，该5AOV-网的拓扑序列是（ ） A. 12345 B. 13245 C. 54231 D. 不能进行拓扑排序31. 一棵含18个结点的二叉树的高度至少为( )。A. 3 B. 4 C. 5 D. 632. 无向图中一个顶点的度是指图中( )。A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数C. 通过该顶点的回路数 D. 与该顶点连通的顶点数33. 有一个二维数组A1:6，0:7 ，每个数组元素用相邻的6个字节存储，存储器按字节编址，假设存储数组元素A1，0的第一个字节的地址是0。若按行存储，则A2，4的第一个字节的地址是（ ）。 A. 72 B. 96 C. 120 D. 234 34. 关键路径是事件结点网络中( )。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路35. 一组记录的排序码为（46，79，56，28，40，100），则利用堆排序（升序）的方法建立的初始堆为（ ）。( 降序 ？ ) A. 79，46，56，28，40，100 B. 28，46，56，79，40，100 C. 100，79，56，28，40，46 D. 100，56，79，40，46，2836. 设某广义表H=（A，（a,b,c,d），则表达式tail(head(tail(H)的值是（ ）；head(head(tail(H) 的值是（ ）；求原子 b 的表达式是（ ）A. A B. a C. c D. (b,c,d) E. d F. head(tail(head(tail(H) G. tail(tail(head(tail(H) 37. 设无向图的顶点个数为n，则该图最多有（ ）条边。(有向图？)An-1 Bn(n-1)/2 C n(n+1)/2 D n(n-1)38. 当初始序列已经按键值有序，用直接插入算法对其进行排序，总的比较次数为( )次，移动记录的次数达到最小值2(n-1)次。A. 1 B. n C. n-1 D. n(n-1)/239. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是( )A. 直接插入排序B. 简单选择排序C. 快速排序D. 归并排序40. 对有15个元素的有序表作二分(折半)查找,则查找A5的比较序列的下标为( ).A. 8、4、5 B. 8、4、6、5 C. 9、4、5 D. 8、4、7、541. 一组记录的排序码为（46，27，56，38，40，9，39），使用间隔d1=2，做一趟希尔排序（升序）后，记录的排序码顺序为（ ）A. 46, 27, 56, 38, 40, 9, 39 B. 39, 9, 40, 27, 46, 38, 56 C. 39, 40, 46, 56, 9, 27, 38 D. 9, 27, 38, 39, 40, 46, 5642. 下列排序算法中，（ ）算法可能会出现当初始数据有序时，话费的时间反而最多。A. 堆排序 B. 冒泡排序 C. 快速排序 D. 希尔排序43. 设有两个串p和q， 求q在p中首次出现的位置的运算称作( ) A 连接 B. 模式匹配 C. 求子串 D. 求串长44. 下列关键字序列中，构成小根堆的是( )A. 84，46，62，41，28，58，15，37B. 84，62，58，46，41，37，28，15C. 15，28，46，37，84，41，58，62D. 15，28，46，37，84，58，62，4145. 散列文件也称为( )A. 顺序文件 B. 索引文件C. 直接存取文件 D. 间接存取文件46. 下面关于线性表的叙述中，错误的是（ ）。A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。47. 链表不具有的特点是 _。 A. 可随机访问任一个元素 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度成正比48. 在有n个结点的二叉链表中，值为非空的链域的个数为_。A. n-1 B. 2n-1 C. n+1 D. 2n+11. 一棵深度为n的满二叉树有_个叶子结点。(当n=5,6,7时，叶子节点个数？)2. 串的三种存储表示：_、堆串存储结构和块链存储结构。3. 数据结构中评价算法的两个重要指标是算法的时间复杂度和_。4. 稀疏矩阵的三元组表表示法的“三元”指的是：该非零元素所在的行下标、该非零元素所在的列下标和_。5. 顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为1次, 最多为_次。6. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需_一个位置。7. 具有 n 个顶点的有向完全图和无向完全图边的数目分别是_和_。8. 顺序查找法（表长度为n）在等概率查找成功时的平均查找长度为_。9. 对于有向图而言，其邻接矩阵第x行元素之和就是图中第x个顶点的_;邻接矩阵第x列元素之和就是图中第x个顶点的_10. 已知在一棵含有 N（N=4） 个结点的树中，只有度为3 的分支结点和度为0的叶子结点，该树含有_个叶子结点。11. 以二分查找方法从长度为6的有序表中查找一个元素时，查找成功时平均查找长度为_。(假定查找每个元素的概率都相等)12. 一棵完全二叉树有999个结点，它的深度是_13. 对1000个数据元素，希望用最快的速度挑选出前10个最大元素，最好选用_的排序方法。14. 线性表是由n（n=0）个同类型数据元素组成的有限序列，具有_、_、_ 的特点。15. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共