《数据结构》-数据结构a卷

数据结构试卷一、选择题（从下列答案选项中选出一个正确答案，每小题2分，共22分1在数据结构中，与所使用的计算机无关的是数据的（）结构。A逻辑B存储C逻辑和存储D物理2若线性表最常用的操作是存取第I个元素及其前驱的值，则采用（）存储方式节省时间。A单链表B双链表C顺序表D单循环链表3已知模式串T“ABCAABBCABCAABDAB”，该模式串的NEXT数组值为（）。A1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1B1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C1，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1D1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，4设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（）。A13B33C18D405一棵含有101个结点的完全二叉树存储在数组BT102中，其中BT0不用，若BTK是叶子结点，则K的最小值是（）。A51B50C49D486稀疏矩阵一般的压缩存储方法有两种，即（）。A二维数组和三维数组B三元组表和散列表C三元组表和十字链表D散列表和十字链表7对顺序存储的18个数据元素（A1A18）的有序表做二分查找，则查找A3的比较序列的下标为。A1，2，3B9，5，2，3_姓名学号学院专业座位号密封线内不答题密封线线C9，5，3D9，4，2，38用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关，这种说法（）。A正确B错误9下列排序算法中，某一趟排序结束后未必能选出一个元素放在最终位置上的是（）。A堆排序B冒泡排序C直接插入排序D快速排序10在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为1，右孩子的平衡因子为0，则应作（）型调整使其平衡。ALLBLRCRLDRR11在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机依此从该缓冲区中取出数据打印，该缓冲区应是一个（）结构。A堆栈B队列C顺序表D链表二、填空题（每空2分，共18分）1以下程序段的时间复杂度是_，其中N为正整数。INTI1WHILEI1|PNULLWHILEPNULLTOPSTTOPP；IFTOP1PSTTOPTOPPRINTF“C”,PDATA；PRINTF“N”2设二叉排序树采用二叉链表存储，以下递归算法从大到小输出二叉排序树结点值（DATA），请将算法补充完整。INORDERBSTBTNODEB/二叉排序树从大到小输出IFBNULLINORDERBSTPRINTF“C”,INORDERBST3下面是一个堆排序算法，请在空白处填上适当内容，使其成为一个完整算法。其中SIFT为筛选算法，原型为VOIDSIFTRECTYPER,INTLOW,INTHIGHVOIDHEAPSORTRECTYPER,INTN/堆排序算法INTIRECTYPETEMPFORII1I/循环建立初始堆SIFT（R,I,N）FORINI2ITEMPR1R1RIRITEMPSIFT（）/重建堆五、算法设计题1本题10分设计一个算法REVERSE，利用环形队列和顺序栈的基本运算将指定队列中的内容逆置。2（本题6分）设计一个算法MATTOLIST，将无向图的邻接矩阵G转换为邻接表G，相关类型定义如下/邻接矩阵相关定义DEFINEMAXV最大顶点个数TYPEDEFSTRUCTINTNOINFOTYPEINFOVERTEXTYPETYPEDEFSTRUCTINTEDGESMAXVMAXVINTN,EVERTEXTYPEVEXSMAXVMGRAPH/邻接表相关定义TYPEDEFSTRUCTANODEINTADJVEXSTRUCTANODENEXTARCINFOTYPEINFOARCNODETYPEDEFSTRUCTVNODEVERTE