《数据结构A卷试题及答案》由会员分享，可在线阅读，更多相关《数据结构A卷试题及答案（10页珍藏版）》请在金锄头文库上搜索。
1、姓名 学号 学院 专业 座位号 ( 密 封 线 内 不 答 题 )密封线线_ _ 数据结构试卷一、 选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分)1. 在数据结构中，与所使用的计算机无关的是数据的（）结构。A. 逻辑B. 存储C. 逻辑和存储D. 物理2. 若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。A. 单链表B. 双链表C. 顺序表D. 单循环链表3. 已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。A. -1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1B. -1，0，0，0，1，
2、1，2，0，0，1，2，3，4，5，6，0，1C. -1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1D. -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，4. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。A. 13B. 33C. 18D. 405. 一棵含有101个结点的完全二叉树存储在数组bt102中，其中bt0不用，若btk是叶子结点，则k的最小值是（ ）。A. 51B. 50C. 49D. 486. 稀疏矩阵一般的压缩存储方法有两种，即（）。A.
3、二维数组和三维数组B. 三元组表和散列表C. 三元组表和十字链表D. 散列表和十字链表7. 对顺序存储的18个数据元素（A1A18）的有序表做二分查找，则查找A3的比较序列的下标为( )。A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关，这种说法（）。A. 正确B. 错误9. 下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是 （）。A. 堆排序B. 冒泡排序C. 直接插入排序D. 快速排序10. 在平衡二叉树中插入一个结点后造成了不平衡
4、，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整使其平衡。A. LLB. LRC. RLD. RR11. 在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该缓冲区应是一个（ ）结构。A. 堆栈B. 队列C. 顺序表D. 链表二、 填空题（每空2分，共18分）1. 以下程序段的时间复杂度是_，其中n为正整数。int i=1;while(i-1|p!=NULL) while(p!=NULL)top+; Sttop=p; ； if(top-1)p=Stt
5、op; top-; printf(“%c”, p-data); ；printf(“n”);2. 设二叉排序树采用二叉链表存储，以下递归算法从大到小输出二叉排序树结点值（data），请将算法补充完整。InOrderBST(BTNode *b) /二叉排序树从大到小输出if(b!=NULL) InOrderBST( ); printf(“%c”, ); InOrderBST( );3. 下面是一个堆排序算法，请在空白处填上适当内容，使其成为一个完整算法。其中sift为筛选算法，原型为：void sift(RecType R, int low , int high);void HeapSort(Re
6、cType R, int n) /堆排序算法int i;RecType temp;for(i= ; i=1; i-) /循环建立初始堆 sift（R, i , n ） for(i=n;i=2;i-)temp=R1;R1=Ri;Ri=temp;sift（ ）; /重建堆五、 算法设计题1. (本题10分)设计一个算法Reverse，利用环形队列和顺序栈的基本运算将指定队列中的内容逆置。2. （本题6分）设计一个算法MatToList，将无向图的邻接矩阵g转换为邻接表G，相关类型定义如下：/邻接矩阵相关定义#define MAXV rear= =qu-front(2)(qu-rear+1)%MaxSize= =qu-front5. n2+n3+n46. 37. head(tail(head(tail(L)三、 解答下列问题（共30分）1.能A BI CGJ MDEHKLF2.A. (29,12,25,10,58,18,51,47)B. (10,18,25,12,29,58,51,47)C. (18,29,25,47,12,58,10,51) 3.10058
