自学考试《高级语言程序设计》习题.docVIP

2010年自学考试《高级语言程序设计》习题 第1部分 引论 二、选择 1．链式存储结构中，每个数据的存储结点里 D 指向邻接存储结点的指针，用以反映数据间的逻辑关系。 A．只能有1个 B．只能有2个 C．只能有3个 D．可以有多个 2．有下面的算法段： for (i=0; in; i++) k++; 其时间复杂度为 B 。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 四、应用 1．给出下面3个算法段的时间复杂度： （1）x++； （2）for (j=1; jn; j++) x++; （3）for (j=1; j=n; j++) for (k=1; k=m; k++) x++; 答：（1）的时间复杂度为O(1)； （2）的时间复杂度O(n)； （3）的时间复杂度是O(n2)。 第2部分 线性表 一、填空 1．以顺序存储结构实现的线性表，被称为 顺序表 。 2．以链式存储结构实现的线性表，被称为 链表 。 3．不带表头结点的链表，是指该链表的表头指针直接指向该链表的 起始结点 。 4．顺序表Sq = (a1，a2，a3，…，an)（n≥1）中，每个数据元素需要占用w个存储单元。若m为元素a1的起始地址，那么元素an的存储地址是 m+(n-1)*w 。 5．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用 顺序 存储结构。 二、选择 1．下面，对非空线性表特点的论述， C 是正确的。 A．所有结点有且只有一个直接前驱 B．所有结点有且只有一个直接后继 C．每个结点至多只有一个直接前驱，至多只有一个直接后继 D．结点间是按照1对多的邻接关系来维系其逻辑关系的 2．带表头结点的单链表Lk_h为空的判定条件是 B 。 A．Lk_h == NULL B．Lk_h-Next == NULL C．Lk_h-Next == Lk_h D．Lk_h != NULL 3．往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动 B 个结点。 A．n B．n/2 C．n+1 D．(n+1)/2 4．在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是 C 。 A．rtr-Next = ptr-Next; ptr-Next = rtr; B．ptr-Next = rtr-Next; C．qtr-Next = rtr; rtr-Next = ptr; D．ptr-Next = rtr; rtr-Next = qtr-Next; 5．在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是 A 。 A．ptr-Next = ptr-Next-Next ; B．ptr = ptr-Next; ptr-Next = ptr-Next-Next ; C．ptr = ptr-Next-Next ; D．ptr-Next= ptr ; 6．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动 B 个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 7．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动 A 个元素。 A．n-i B．n-i+1 C．n-i-1 D．i 8．设tail是指向一个非空带表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是 D 。 A．ptr = tail ; B．tail = tail-Next ; tail = tail-Next ; free (tail) ; free (ptr); C．tail = tail-Next-Next ; D．ptr = tail-Next-Next ; Free (tail); tail-Next-Next = ptr-Next ; Free (ptr); free (ptr); 9．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是 B 。 A．qtr-Next = ptr ; B