数据结构期中试卷A一、判断题：（10分，每题1分）1、线性表的逻辑顺序与物理顺序总是一致的。()2、线性表中的每个结点最多只有一个前驱和一个后继。（）3、单链表从任何一个结点出发，都能访问到所有结点。（）4、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。（）5、用一组地址连续的存储单元存放的元素一定构成线性表。（）6、算法一定要有输入和输出。（）7、若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（）8、符号p->next出现在表达式中表示p所指的那个结点的内容。（）9、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（）10、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（）二、填空题：（10分，每空1分）1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。2、若频繁地对线性表进行插入与删除操作，该线性表应采用______________存储结构。3、在双向链表中，每个结点含有两个指针域，一个指向_________结点，另一个指向________结点。4、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是___________。5、某带头结点的单链表的头指针head，判定该单链表非空的条件______________。6、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用________。7、______链表从任何一个结点出发，都能访问到所有结点。8、广义表（A,(a,b),d,e,((i,j),k)）,则广义表的长度为________，深度为_______。三、选择题：（30分，每题2分）（1）在栈中存取数据的原则是。A、先进先出B、后进先出C、先进后出D、随意进出（2）已知广义表的表头为A，表尾为(B,C)，则此广义表为________A、（A,(B,C)）B、（A,B,C）C、(A,B,C)D、((A,B,C))（3）二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______A、470B、471C、472D、473（4）在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行____。A、q一>next=p一>next；p一>next=q；B、q一>next=p一>next；p一>next=q；C、p一>next=q一>next；q=p；D、p一>next=q一>next；q一>next=p；（5）在一个顺序队列中，队首指针指向队首元素的____位置。A、前一个B、后一个C、当前D、最后一个（6）如下陈述中正确的是________A、串是一种特殊的线性表B、串的长度必须大于零C、串中元素只能是字母D、空串就是空白串（7）一个非空广义表的表头________A、不可能是子表B、只能是子表C、只能是原子D、可以是子表或原子（8）线性表若采用链表存储结构时，要求内存中可用存储单元的地址________Ａ、必须是连续的Ｂ、部分地址必须是连续的Ｃ、一定是不连续的Ｄ、连续不连续都可以（9）下面程序段的时间复杂度为____________。for(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)（10）在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移_____个元素。A、n-iB、n-i+1C、n-i-1D、i（11）当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为_____。A、N-2B、N-1C、ND、N+1（12）链式栈与顺序栈相比，一个比较明显的优点是________。A、插入操作更加方便B、通常不会出现栈满的情况C、不会出现栈空的情况D、删除操作更加方便（13）由两个栈共享一个向量空间的好处是______。A、减少存取时间,降低下溢发生的机率B、节省存储空间,降低上溢发生的机率C、减少存取时间,降低上溢发生的机率D、节省存储空间,降低下溢发生的机率（14）计算机识别、存储和加工处理的对象被统称为_________A、数据B、数据元素C、数据结构D、数据类型（15）在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________A