A:问题规模 B:计算机硬件性能 C:编译程序质量 D:程序设计语言 答案: 问题规模
本门课程完整答案:点击这里,查看 数据结构(西北大学) 中国大学mooc答案满分完整版章节测验 m106290
A:算法是否具有较好的可读性 B:算法中是否存在语法错误 C:算法的功能是否符合要求 D:算法的执行时间与所需空间与问题规模的关系 答案: 算法的执行时间与所需空间与问题规模的关系
A:找出数据结构的合理性 B:研究算法中输入和输出的关系 C:分析算法的时空效率以求改进 D:分析算法的可读性 答案: 分析算法的时空效率以求改进
A:数据项 B:数据类型 C:数据元素 D:数据变量 答案: 数据项
A:问题规模是nn B:问题规模与nn正比 C:执行时间与nn正比 D:执行时间等于nn 答案: 执行时间与nn正比
A:nn B:n(n-1)/2 C:n(n+1)/2 D:n(n-1) 答案: n*(n-1)/2
A:O(1) B:O(nn+n) C:O(n) D:O(nn) 答案: O(n*n)
A:O(n-i+1) B:O(n-i) C:O(n) D:无法确定 答案: O(n)
A:O(n) B:O(100) C:O(1) D:O(n*n) 答案: O(1)
A:O(n) B:O(1) C:O(sqrt(n)) sqrt表示对n取根方 D:O(n-i) 答案: O(sqrt(n)) sqrt表示对n取根方
A:T(n) = O(nnn) B:T(n) = O(nn) C:T(n) = O( (nnn+nn+n)/n ) D:T(n) = O(nn+n) 答案: T(n) = O(nn)
A:数据 B:数据对象 C:数据元素 D:数据项 答案: 数据元素
A:集合 B:线性 C:树 D:图 答案: 集合; 线性; 树; 图
A:0个或多个输入;至少1个输出 B:正确性 C:确定性 D:可行性和有限性 答案: 0个或多个输入;至少1个输出; 确定性; 可行性和有限性
A:正确性 B:可读性 C:健壮性 D:高效率和低存储 答案: 正确性; 可读性; 健壮性; 高效率和低存储
A:顺序存储 B:非顺序存储 C:图结构 D:树结构 答案: 顺序存储; 非顺序存储
A:一个数据对象 B:元素的存储结构 C:元素间的关系 D:一组操作 答案: 一个数据对象; 元素间的关系; 一组操作
A:正确 B:错误 答案: 错误 分析:线性、非线性结构是元素间的逻辑关系。 顺序、非顺序存储时元素的存储结构。 二者没有明显的一一对应关系。
也就是说,无论元素的逻辑关系如何,顺序和非顺序存储结构都是可以的。
A:正确 B:错误 答案: 错误 分析:程序是用某种程序设计语言对算法的实现。二者不同。
A:正确 B:错误 答案: 正确
A:正确 B:错误 答案: 错误 分析:可行性指算法咋原则上要能实现;每一条指令需要由明确含义是算法的确定性。
A:正确 B:错误 答案: 错误 分析:二者是算法的设计要求,但不是全部。还包括正确性、可读性、鲁棒性(健壮性)
A:正确 B:错误 答案: 错误 分析:数据类型是一组性质相同的元素及在其上的一组操作的总称。其并不占内存空间。 而变量是某种数据类型具体表现,需要占内存空间。
A:正确 B:错误 答案: 错误 分析:哪种存储结构更优,取决于其操作。二者各有优缺点。
A:正确 B:错误 答案: 错误 分析:还有集合结构,既不属于线性,也不属于非线性。集合结构中,元素间没有任何关系。
A:O(logn)(以2为底) B:O(1) C:O(n) D:O(n*n) 答案: O(n)
A:n-i B:i C:n-i+1 D:n-i-1 答案: n-i+1
A:插入、删除不需要移动元素 B:可随机访问任一元素 C:不必事先估计存储空间 D:所需存储空间与线性表程度成正比 答案: 可随机访问任一元素
A:p->next=p->next->next; free(p->next); B:free(p->next);p->next=p->next->next; C: p=p->next; D:s=p->next;p->next=s->next;free(s); 答案: s=p->next;p->next=s->next;free(s);
A:n B:(n+1)/2 C:(n-1)/2 D:n/2 答案: (n-1)/2
A:Base+(i-1)×m B:Base+i×m C:Base-i×m D:Base+(i+1)×m 答案: Base+(i-1)×m
A:i>0 B:1≤i≤n+1 C:1≤i≤n-1 D:0≤i≤n+1 答案: 1≤i≤n+1
A:p==NULL B:p->next==NULL C:p->next==P D:p->next!=NULL 答案: p->next==NULL
A:504 B:508 C:516 D:528 答案: 528
A:n-i B:n-i+1 C:n-i-1 D:i 答案: n-i
A:O(1) B:O(n) C:O(logn)(以2为底) D:O(nlogn) 答案: O(1)
A:i++ B:j++ C:i– D:j– 答案: j++
A:free(p); pre->next=p->next; B:free(p->next);pre->next=p->next; C:pre->next=p->next; free(p); D:p->next=pre->next;free(p); 答案: pre->next=p->next; free(p);
A:正确 B:错误 答案: 错误 分析:添加头结点的目的是,简化操作,使得在表头和中间位置对链表的操作统一化。不一定是为了存储链表的长度。
A:正确 B:错误 答案: 错误
A:正确 B:错误 答案: 错误 分析:顺序表中,查找第i个元素,时间是常量。
A:正确 B:错误 答案: 错误 分析:首元素没有前驱,尾元素没有后继。
A:正确 B:错误 答案: 错误 分析:两种存储结构各有优缺点。要根据实际问题选择合适的存储结构。
A:正确 B:错误 答案: 错误 分析:前半句正确,后半句错误。 顺序存储中,插入和删除的效率比较低。
A:正确 B:错误 答案: 错误 分析:数组本身不能进行插入和删除,因为数组的长度是不可变的。(在某些语言中)
A:p->next==NULL B:p==NULL C:p->next==L D:p==L 答案: p->next==L
A:顺序表 B:双向链表 C:带头结点的双循环链表 D:单循环链表 答案: 顺序表
A:单链表 B:仅有头指针的单循环链表 C:双链表 D:带尾指针的单循环链表 答案: 带尾指针的单循环链表
A:2 B:3 C:4 D:5 答案: 4
A:O(m) B:O(n) C:O(m+n) D:O(m*n) 答案: O(n)
A:1 B:2 C:3 D:4 答案: 2
A:p->prior->next = p->next B:p->next = p->prior C:p->prior = p->next D:p->prior->next = p 答案: p->prior->next = p->next
A:s->next=p->next;p->next=s; //将s结点插入到p之后t=s->data;s->data=p->data;p->data; //s结点和p结点的值互换 B:q=p->next;while(q->next!=p) q=q->next;s->next=p; q->next=s; C:q=p->next;while(q->next!=p) q=q->next;q->next=s; s->next=p; D:在p结点前插入s结点,而且要求在O(1)内,无法实现。 答案: s->next=p->next;p->next=s; //将s结点插入到p之后t=s->data;s->data=p->data;p->data; //s结点和p结点的值互换
A:可采用以下算法实现:第一步:先将两个链表各自遍历一遍,统计出两个单链表的长度m和n。假设m>n,k=m-n第二步:长链表先走k步:用指针p从长链表头开始,先走k步,此时p指向长链表的第k+1个结点。第三步:q从短链表头开始,和p一起走。p和q相等时,即为交点;如果p和q不相交,则两个链表不相交。 B:可采用以下算法实现:第一步:用两个指针p和q,分别从两个链表头开始,向后走。第二步:如果两个指针相等,即指向同一个结点,则说明相交,该结点就是交点。 C:可采用以下算法实现:第一步:将两个链表分别逆置。第二步:从头开始,什么时候链表分叉,该分叉的结点就是相交的结点。 D:该问题无法求解。 答案: 可采用以下算法实现:第一步:先将两个链表各自遍历一遍,统计出两个单链表的长度m和n。假设m>n,k=m-n第二步:长链表先走k步:用指针p从长链表头开始,先走k步,此时p指向长链表的第k+1个结点。第三步:q从短链表头开始,和p一起走。p和q相等时,即为交点;如果p和q不相交,则两个链表不相交。
A:采用快慢指针方法。即:第一步:一个指针走的快,每次走2个结点;一个指针走的慢,每次走1个结点。第二步:当快指针到结尾或空时,慢指针所指结点即为中间结点。注:遇到链表结点为奇数或偶数时,需稍加改进即可。 B:第一步:遍历一遍链表,求出其长度n。第二步:再从头开始遍历链表,到n/2处即可。若n为偶数,中间结点则有2个;若n为奇数,则只有1个。需稍加处理。 C:第一步:将链表中的结点依次放入一个数组中,同时记录结点个数;第二步:数组中间位置即为中间结点。 D:无法实现 答案: 采用快慢指针方法。即:第一步:一个指针走的快,每次走2个结点;一个指针走的慢,每次走1个结点。第二步:当快指针到结尾或空时,慢指针所指结点即为中间结点。注:遇到链表结点为奇数或偶数时,需稍加改进即可。
A:第一步:将单链表逆置;第二步:输出单链表中的元素;第三步:将单链表逆置,即恢复之前的单链表。 B:第一步:将单链表中的 元素依次放入一个数组中第二步:逆序输出该数组中的元素。 C:可用如下代码实现:void reversePrint(Node *p//p初值为单链表第一个结点{ while(p!=NULL) { reversePrint(p->next); printf(“%c “,p->data); //假设结点值为字符} D:算法思想:第一步:从头到尾找到最后一个结点;第二步:从最后一个结点向前依次输出每个结点的值。 答案: 算法思想:第一步:从头到尾找到最后一个结点;第二步:从最后一个结点向前依次输出每个结点的值。
A:正确 B:错误 答案: 错误 分析:静态链表本质仍然是链表,所以它不具有顺序表的优点。
A:正确 B:错误 答案: 错误 分析:前驱和后继是元素间的逻辑关系。 循环单链表是元素的存储关系,只是为了操作方便而采用循环链表,并不会改变元素的逻辑关系。