工大数据结构第二章作业(共68页).docx

精选优质文档-----倾情为你奉上数据结构与算法上机作业第二章 线性表一、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为 A. O(log2n) B. O(1) C. O(n) D. O(n2)2、以下关于线性表的说法中，不正确的是 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C. 线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表） D. 存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现）3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 A. O(1) B. O(n) C. O(n2) D. O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 A. n B. (n-1)/2 C. n/2 D. (n+1)/2已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.i的取值服从1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移动N/2个结点 期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为 。

A. n B. n/2 C. (n+1)/2 D. (n-1)/26、在顺序表中，只要知道 ，就可以求出任一结点的存储地址 A. 基地址 B. 结点大小 C. 向量大小 D. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 A. n B. 2n-1 C. 2n D. n-18、线性表采用链表存储时其存储地址要求 A. 必须是连续的 B. 部分地址必须是连续的 C. 必须是不连续的 D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是 A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 A. O(1) B. O(n) C. O(n2) D. O(log2n)11、 语句是 。

A. HL=p; p->next=HL; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p;HL为链表的头指针HL指示链表中第一个节点的存储位置，在表头插入一个由指针p指向的节点后，头指针指向p，p的指针域指向原链表中第一个节点12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是 A. p=q->next; p->next=q->next; B. p=q->next; q->next=p; C. p=q->next; q->next=p->next; D. q->next=q->next->next; q->next=q;？13、设有编号为1, 2, 3, 4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出栈顺序为 A. 1234 B. 1243 C. 1324 D. 1423至少有14种①全进之后再出情况只有1种：4，3，2，1②进3个后再出的情况有3种3,4,2,1 3,2,4,1 3,2,1,4③进2个后再出的情况有5种2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4④进1个后再出的情况，有5种1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,314、4个元素按A, B, C, D顺序进入S栈，执行两次Pop(S, x)运算后，栈顶元素的值是 。

A. A B. B C. C D. D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 命令 A. x=top; top=top->next; B. top=top->next; x=top->data; C. x=top->data; D. x=top->data; top=top->next;16、向顺序栈中输入元素时 A. 先存入元素，后移动栈顶指针 B. 先移动栈顶指针，后存入元素 C. 谁先谁后无关紧要 D. 同时进行17、设有一个顺序栈，元素A, B, C, D, E, F依次进栈，如果6个元素出栈的顺序是B, D, C, F, E, A，则栈的容量至少为 A. 3 B. 4 C. 5 D. 6顺序如下A入栈B入栈然后B出栈,C入栈D入栈,D出栈,C出栈,E入栈,F入栈,F出栈,E出栈.栈里元素最多时候就是acd和aef,所以3个就够了18、设已将元素A, B, C依次入栈，元素D正等待进栈那么下列4个序列中不可能出现的出栈顺序为 。

A. CADB B. CBDA C. CDBA D. DCBA19、栈和队列的相同之处是 A.元素的进出满足先进后出 B.元素的进出满足后进先出 C.只允许在端点进行插入和删除操作 D.无共同点 栈Insert(L,n+1,x)Delete(L,n)而栈只允许在表尾一端进行插入和删除队列Insert(L,n+1,x)Delete(L,1)队列只允许在表尾一端进行插入，在表头一端进行删除20、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 A. 6 B. 4 C. 3 D. 2 设栈长度为s,起始为0因为栈后进先出,队列先进先出.又因为元素E1..E6是顺序入栈,那么分析过程如下：按照出栈过程分析,因为给定出栈顺序：E2,E4,E3,E6,E5,E1,E2要进栈,所以E1必须进栈,进栈顺序：E1,E2,所以s为2下面E2出栈,打印出E2,剩余结果为E4,E3,E6,E5,E1,因为E2出栈了,所以当前栈容量为2,但是只是用了1个,存放E1,下面继续E3进栈,E4进栈,此时s为3,根据出栈结果,那么E4出栈,E3出栈,此时栈容量为3但是只有E1在栈中,剩余结果为E6,E5,E1,同理,E5进栈,E6进栈,此时栈被填满,容量为3,后E6出栈,E5出栈,E1出栈,栈空,容量为3.所以S的容量至少为3.21、队列通常采用的两种存储结构是( )。

A. 顺序存储结构和链式存储结构 B.散列方式和索引方式C. 链表存储结构和线性存储结构 D.线性存储结构和非线性存储结构22、循环队列SQ队满的条件是 A. SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front B. SQ->rear==0 D. SQ->front==0队空:Q.front=Q.rear 队满:(Q.rear+1)%MAXQSIZE=Q.front23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 A. 5和1 B. 4和2 C. 2和4 D. 1和524、链栈与顺序栈相比，有一个较为明显的优点是 A. 通常不会出现满栈的情况 B. 通常不会出现栈空的情况 C. 插入操作更加方便 D. 删除操作更加方便25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为 。

A. 42 B. 16 C. 17 D. 4126、串是一种特殊的线性表，其特殊性体现在 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个字符27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为 A. O(m) B. O(n) C.O(m+n) D. O(mn)28、已知串S=“abab”，其Next数组值为 A. 0123 B. 0121 C. 0112 D. 012229、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为 A. 20% B. 40% C. 50% D. 33.3%存储密度;结点数据本身所占的存储量/结点结构所占的存储量 1/（1+3）30、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是 A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q; B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior; C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q; D. q->Prior=p->Prior; q->Next=q; p->Prior=q; p->Next=q;31、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 。

A. 0, 0 B. 0, n-1 C. n-1, 0 D. n-1, n-132、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是 A. bacde B. dbace C. dbcae D. ecbad33、在双向链表中间插入一个结点时，需要修改修改 个指针域 A. 1 B. 2 C. 3 D. 434、在按行优先。