资源描述：
《哈尔滨工程大学-考研数据结构真题-7.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1．算法的时间复杂度取决于。A．问题的规模B.待处理数据的初态C.A和B2．链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3．在双向链表存储结构中，删除p所指的结点时须修改指针。A．p->prior->next=p->next；p->next->prior=p->prior；B．p->prior
2、=p->prior->prior；p->prior->next=p；C．p->next->prior=p；p->next=p->next->next；D．p->next=p->prior->next；p->prior=p->next->next；4．输入序列为ABC，可以变为CBA时，经过的栈操作为。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push
3、,push,pop,pop5．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是。A．6B.4C.3D.26．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为。A.13B.33C.18D.407．广义表运算式GetTail(((a,b),(c,d)))的操作结果是。A.(
4、c,d)B.c,dC.((c,d))D.d8．对n个元素的表做顺序查找时，若查找每个元素的概率相同，则查找成功的平均查找长度为。A．(n+1)/2B.n/2C.nD.((1+n)×n)/29．设有一表示算术表达式的二叉树，它所表示的算术表达式是。A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+(F-G))D.A*B+C/D*E+F-G10．一棵树高为K的完全二叉树至少有个结点。A．2k–1B.2k-1–1C.2k-1D.2k11．若二
5、叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用遍历方法最合适。A．先序B．中序C．后序D．按层次12．下面结构中最适于表示稀疏无向图的是。A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表13．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作型调整以使其平衡。A.LLB.LRC.RLD.RR第5页共6页第6页共6页班级：学号：姓名：装订线14．数据序列（2，1，4，9，8，10，6，20）只能是下
6、列排序算法中的的两趟排序后的结果。A.快速排序B.冒泡排序C.选择排序D.插入排序15．对下列关键字序列用快速排序法进行排序时，速度最快的情形是。A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}D．{5,9,17,21,23,25,30}二、填空题（每空1分，共10分）1．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是。2．设有二维数组A[0.
7、.9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为_______。3．当广义表中的每个元素都是原子时，广义表便成了_______。4．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_______。5．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_______。6．已知一无向图G=（V，E），其中V={a，b，c，d，e}，E={(a,b)，(a
8、,d)，(a,c)，(d,c)，(b,e)}，现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_______遍历方法。7.己知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找100时，需_______次才能确定不成功。8．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______。9．分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是____
