●试题三
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数diff的功能是:根据两个由整数(都大于-32768)按升序构成的单链表L1和L2(分别由A,B指向)构造一个单链表L3(由*r指向),要求L3中的所有整数都是L1,并且不是L2中的整数,还要求L3中的所有整数都两两不等。
【函数】
#include<mallo
C.h>
typedef struct node{
int d;
struct node *next
}Node;
void diff(Node *A,Node *B,Node **r)
{
int lastnum;
Node*p;
*r=NULL;
if(!A)return;
while((1) )
if(A->d<B->d)
{
lastnum=A->d;
p=(Node*)malloc(sizeof(Node));
p->d=lastnum;
p->next=*r; (2) ;
do
A=A->next;
while((3) );
}
else if(A->d>B->d)
B=B->next;
else{
(4) ;
lastnum=A->d;
while (A && A->d==lastnum)A=A->next;
}
while(A)
{
lastnum=A->d;
p=(Node*)malloc(sizeof(Node));
p->d=lastnum;
(5) ;
*r=p;
while (A && A->d==lastnum) A=A->next;
}
}
系统中一个程序结构如图5所示:
该程序有4条不同路径,分别为L1:a→c→e;L2:a→b→d;L3:a→b→e;L4:a→c→d。小王设计了4组测试用例:
①【(1,0,3),(1,0,4)】覆盖abe;【(2,1,1),(2,1,2)】覆盖abe;
②【(2,1,1),(2,1,2)】覆盖abe;【(3,0,3),(3,0,1)】覆盖acd;
③【(2,0,4),(2,0,3)】覆盖ace;【(1,0,3),(1,0,4)】覆盖abe;
【(2,1,1),(2,1,2)】覆盖abe;【(1,l,1),(1,1,1)】覆盖abd;
④【(2,0,4),(2,0,3)】覆盖ace;【(1,1,1),(1,1,1)】覆盖abd;
【(1,1,2),(1,1,3)】覆盖abe;【(3,0,3),(3,0,1)】覆盖acd;
这4组测试用例中 (5) 属于判定覆盖; (6) 属于条件覆盖; (7) 属于路径覆盖; (8) 属于条件组合覆盖(注:该题测试用例格式为【(A,B,X)输入,(A,B,X)输出】)。
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。
【说明】
函数diff的功能是:根据两个由整数(都大于-32768)按升序构成的单链表L1和L2(分别由A,B指向)构造一个单链表L3(由*r指向),要求13中的所有整数都是L1,并且不是 L2中的整数,还要求L3中的所有整数都两两不等。
【函数】
include < malloc. h >
typedef struct node {
int d;
struct node * next
} Node;
void diff(Node *A,Node * B,Node * * r)
{
int lastnum;
Node * p;
*r = NULL;
if(! A) return;
while((1))
if(A->d < B ->d)
{
lastnum =A -> d;
p= (Node * ) malloc(sizeof(Node) );
p->d = lastnum;
p->next= *r;(2);
do
A = A -> next;
while((3));
}
else if(A->d > B->d)
B=B- >next;
else {
(4);
lastnum=A -> d;
while (A && A->d = = lastnum) A=A-> next;
}
while(A)
{
lastnum=A->d;
p=(Node * ) malloc(sizeof(Node) );
p-> d = lastnum;
(5);
*r=p;
while (A && A->d = = lastnum) A=A->next;
}
}
分析该问题,发现问题具有最优子结构。以 L1为例,除了第一个工位之外,经过第j个工位的最短时间包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间,如式(1)。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式(2)。
由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间,该问题具有重复子问题的性质,故采用迭代方法求解。
该问题采用的算法设计策略是(),算法的时间复杂度为()
以下是一个装配调度实例,其最短的装配时间为(),装配路线为()
A.分治
B.动态规划
C.贪心
D.回溯
A. O(lgn)
B. O(n)
C. O(n2)
D. O(nlgn)
A.21
B.23
C.20
D.26
A.S11→S12→S13
B.S11→S22→S13
C.S21→S12→S23
D.S21→S22→S23
阅读以下应用说明、图和C++程序,将C++程序中(1)~(6)空缺处的语句填写完整。
【说明】
以下【C++程序】用于实现两个多项式的乘积运算。多项式的每一项由类Item描述,而多项式由类List描述。类List的成员函数主要有:
createList():创建按指数降序链接的多项式链表,以表示多项式:
reverseList():将多项式链表的表元链接顺序颠倒:
multiplyList(ListL1,ListL2)计算多项式L1和多项式L2的乘积多项式。
【C++程序】
include <iostream.h>
class List;
class Item {
friend class List;
private:
double quot ;
int exp ;
Item *next;
Public:
Item(double_quot,int_exp)
{ (1) ;}
};
class List{
private:
Item *list;
Public:
List(){
list=NULL:
}
void reverseList();
void multiplyList(List L1,List L2);
void createList();
};
void List::createList()
{ Item *p,*U,*pre;
int exp;
double quot;
list = NULL;
while (1) {
cout << "输入多项式中的一项(系数、指数) :" << endl;
cin >> quot >> exp:
if (exp<0 )
break ; //指数小于零,结束输入
if (quot=0 )
continue;
p = list;
while ((2) ) { //查找插入点
pre = p;
p = p->next;
}
if (p != NULL && exp = p->exp ) {
p->quot += quot;
continue ;
}
u =(3);
if (p == list)
list = u;
else
pre->next = u;
u ->next = p;
}
}
void List::reverseList()
{ Item *p, *u;
if (list==NULL )
return;
p = list ->next;
list -> next = NULL;
while (p != NULL) {
u = p -> next;
p ->next = list;
list = p;
p = u;
}
}
void List::multiplyList (List L1, List L2 )
{ Item *pL1,*pL2,*u;
int k, maxExp;
double quot;
maxExp =(4):
L2.reverseList();
list=NULL;
for (k = maxExp;k >= 0;k-- ){
pL1 = L1.list;
while (pL1 != NULL && pL1 -> exp > k )
pL1 = pL1 ->next;
pL2 = L2.1ist;
while (pL2 NULL &&(5))
pL2 = pL2 -> next;
quot = 0.0;
while (pL1 != NULL && pL2 != NULL){
if(pL1->exp+pL2->exp==k) {
(6)
pL1 = pL1 -> next;
pL2 = pL2 -> next;
} else if (pL1 -> exp + pL2 -> exp > k )
pL1 = pL1 -> next;
else
pL2 = pL2 -> next;
}
if (quot !=0.0 ) {
u = new item(quot, k );
u -> next = list;
list = u;
}
}
reverseList ();
L2. reverseList ():
}
void main()
{ List L1,L2,L;
PC机中CPU执行MOV指令从存储器读取数据时,数据搜索的顺序是()。
A.从L1 Cache开始,然后依次为L2 Cache、DRAM和外设
B.从L2 Cache开始,然后依次为L1 Cache、DRAM和外设
C.从外设开始,然后依次为DRAM、L2 Cache和L1 Cache
D.从外设开始,然后依次为DRAM、L1 Cache和L2 Cache
PC中CPU执行MOV指令从存储器读取数据时,数据搜索的顺序是()。
A.L1 Cache、L2 Cache、DRAM和外设
B.L2 Cache、L1 Cache、DRAM和外设
C.DRAM、外设、L2 Cache和L1 Cache
D.外设、DRAM、L1 Cache和L2 Cache
A.收敛于原点
B.发散到无穷
C.沿矩形边界稳定地转圈
D.随机运动
平面坐标系内,有直线L1:y=ax和直线L2:y=bx(a>b>0),动点(1,0)沿逆时针方向绕原点做如下运动:先沿垂直方向到达直线L1,再沿水平方向到达直线L2,又沿垂直方向到达直线L1,再沿水平方向到达直线L2,…,依次交替沿垂直和水平方向到达直线L1和L2。这样的动点将______。
A.收敛于原点
B.发敞到无穷
C.沿矩形边界稳定地转圈
D.随机运动
A.寄存器、内存、外存
B.寄存器、Cache、内存
C.Cache、主存、辅存
D.L0、L1、L2三级Cache