《数据结构》期中试题

PAGEPAGE1南京大学金陵学院期中试卷2007~2008学年第二学期课程名称：《数据结构》教师姓名：彭成磊试卷类型：开学号：__________姓名：_________专业：___________成绩：_____一、选择题（共16题，每题2.5分，计40分）1.组成数据的基本单位是（）A．数据项 B．数据类型 C．数据元素 D．数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。A．理想结构，物理结构 B．理想结构，抽象结构C．物理结构，逻辑结构 D．抽象结构，逻辑结构3.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A．64 B．63 C．63.5 D．75.线性表采用链式存储结构时，其地址（）。A．必须是连续的 B．部分地址必须是连续的C．一定是不连续的 D．连续与否均可以6.在一个单链表中，若删除p所指结点的后续结点，则执行（）。A．p->next=p->next->next; B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;7.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。A．edcba B．decba C．dceab D．abcde8.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,19.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（）。A．rear－qulen B．rear－qulen＋mC．m－qulen D．1＋（rear＋m－qulen）%m10.下列关于串的叙述中，正确的是（）A．一个串的字符个数即该串的长度 B．一个串的长度至少是1C．空串是由一个空格字符组成的串 D．两个串S1和S2若长度相同，则这两个串相等11.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。A．SA+141 B．SA+144 C．SA+222 D．SA+22512.稀疏矩阵一般的压缩存储方法有两种,即（）和十字链表。A．二维数组 B．三维数组 C．三元组 D．散列13.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n+1)/2]中,对下三角部分中任一元素ai,j(i>=j)(1=<i,j<=n),在一组数组B的下标位置k的值是（）。A．i(i-1)/2+j-1 B．i(i-1)/2+j C．i(i+1)/2+j-1 D．i(i+1)/2+j14.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（）。A．2h B．2h-1 C．2h+1 D．h+115.已知某二叉树的后序遍历序列是dabec。中序遍历序列是deabc,它的前序遍历序列是（）。A．acbed B．decab C．deabc D．cedba16.对一个满二叉树,m个树叶,n个结点,深度为h,则（）。A．n=h+m B．h+m=2n C．m=h-1 D．n=2^h-1二、判断题（共6题，每题2.5分，计15分）1.算法就是程序。（）2.数据元素是数据的最小单位。（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（）4.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）5.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值（）6.二叉树中任何一个结点的度都是2。（）三、填空题（共18空，每空2.5分，计45分）1.线性结构中元素之间存在________关系,树形结构中元素之间存在________关系,图形结构中元素之间存在________关系。2.算法的五个重要特性是________、________、________、________、________。3.设有一批数据元素,为了最快的存储某元素,数据结构宜用________结构,为了方便插入一个元素,数据结构宜用________结构。4.顺序表中逻辑上相邻的元素物理位置()相邻，单链表中逻辑上相邻的元素物理位置________相邻。5.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;_______________;6.已知L是无表头结点的单链表，请从下列提供的答案中选择合适的语句序列，实现表尾插入s结点________。A．p->next=s; B．p=L; C．L=s;D．p->next=s->next; E．s->next=p->next;F．s->next=L; G．s->next=null; H．while(p->next!=0)p=p->next;I．while(p->next!=null)p=p->next;7.栈的特点是______________，队列的特点是________________。8.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳________个元素。9.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是________。10.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有________个。20080423数据结构期中考试参考答案选择1.C2.C3.C5.D6.A7.C8.B9.D10.A