搜索
北方工业大学《数据结构》课程期末复习材料（2016-2017学年度）一、选择（填空）题（第一、二、三章）...........................................................................1二、选择（填空）题（第四、五、六章）...........................................................................3三、选择（填空）题（第七、九、十章）...........................................................................4四、判断题（第一、二、三章）...........................................................................................5五、判断题（第四、五、六章）...........................................................................................6六、判断题（第七、九、十章）...........................................................................................6七、计算简答题（第二章）...................................................................................................7八、计算简答题（第三章）...................................................................................................9九、计算简答题（第四章）.................................................................................................10十、计算简答题（第六章）.................................................................................................11十一、计算简答题（第七章）.............................................................................................12十二、计算简答题（第九章）.............................................................................................15十三、计算简答题（第十章）.............................................................................................16答案解析.........................................................................................................................................18北方工业大学计算机学院二〇一六年十二月1一、选择（填空）题（第一、二、三章）1.一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C2.以下数据结构中，（）是非线性数据结构A.树B.字符串C.队D.栈3.下面关于线性表的叙述中，错误的是（）？A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。4.在一个长度为n的顺序表中，在第i（0i=n+1）个元素之前插入一个元素时，需向后移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i5.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7.链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比8.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）9.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)10.在一个单循环链表(长度为n)中，已知p指针指向链表中一个非空结点，现要删除链表中p指针所指结点，其时间复杂度为（）。A.O(n)B.O(1)C.O(n2)D.不确定11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)12.非空的循环链表head的尾结点p↑满足（）A．p-next=headB．P-next=NULLC．p=NULLD．p=head13.带头结点的循环链表L为空的条件是（）。A.L==NULLB.L-next==NULLC.L-next==LD.L-next==L-next14.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;215.在双向链表指针p的结点前插入一个指针q的结点操作是()。A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;16.若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是()。A.iB.n-iC.n-i+1D.不确定17.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i18.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.23415619.设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，420.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点21.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m22.设循环队列存储空间的下标范围是0..n-1，当队列尾指针为rear（初始时rear=0），队列长度为len时，循环队列中队头元素所在位置为_________。A.rear-lenB.rear–len+1C.(rear–len+1)%nD.(rear–len+n)%n23.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)24.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front25.执行完下列语句段后，i值为：（）intf(intx){inty;y=((x0)?x*f(x-1):2);printf(%d,y);returny;}inti;i=f(f(1));A．2B.4C.8D.无限递归326.程序段：c=0;for(i=0;im;i++)for(j=0;jn;j++)c=c+i*j;的时间复杂度为＿＿＿＿A）O(m2)B）O(n2)C）O(m×n)D）O(m+n)27.若输入序列为1，2，3，4，借助于一个输入受限的双向队列，不可能得到的输出序列为＿＿。A）2，4，3，1B）3，1，2，4C）4，1，3，2D）4，2，3，1二、选择（填空）题（第四、五、六章）1.下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串B.联接C.匹配D.求串长3.已知串S=‘aaab’,其Next数组值为（）A．0123B．1123C．1231D．1211。4.串‘ababaaababaa’的next数组为（）。A.012345678999B012121111212C.011234223456D.01230123223455.串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数6.字符串‘ababaabab’的nextval为（）。A.(0,1,0,1,0,4,1,0,1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)7.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）A.13B.33C.18D.408.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）A.808B.818C.1010D.10209.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。A.1175B.1180C.1205D.121010.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]11.对稀疏矩阵进行压缩存储目的是（）。A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复